%%In this chapter we present two key analyses introduced in the \mclab toolkit as
%part of the \mixten compiler, and are reusable by other compilers built on top
%of the \mclab toolkit. The first analysis is the \emph{IntegerOkay} analysis
%that identifies the variables in the \matlab program that can be safely
%declared as integer in a statically typed target language like \xten, thus
%eliminating the performance overhead associated with otherwise necessary double
%to integer typecasts. The second analysis, called \emph{isComplex} analysis,
%identifies the numerical values in the source \matlab program that are of
%complex type, thus enabling support for code generation for programs that
%involve complex numerical values.
%
%\section{Safely using integer variables: \emph{IntegerOkay}
%Analysis}\label{sec:intok}

In this chapter we present the \emph{IntegerOkay} analysis to identify
which variables in the source \matlab program can be safely declared to
be of an integer type instead of the default double type. In \matlab all
the variables holding a numerical value are by default of type
\texttt{Double}, which means that by default, in the \xten code
generated from \matlab, all variables are statically declared to be of
\texttt{Double}. However, in languages like \xten, Java and C++, certain
program operations require the variables used to be of an integer type.
A prominent example of such an operation is an array access operation.
An array access requires the variables used to index into the array to
be of an integer type. For example, in a statement like \texttt{x =
A(i,j)}, the variables \texttt{i} and \texttt{j} are required to be of
integer type and result in an error otherwise.

\section{Need for Declaring Variables to be of Integer Type}

A simple solution to handle this problem in the generated code from
\matlab is to explicitly cast the variable from \texttt{Double} to
\texttt{Long}, whenever it is required to be used as an integer.
However, our experiments showed this approach to be very inefficient.
With this approach, we observed that the C++ programs generated by the
\xten compiler's C++ backend were slow, and often
even slower than the Java code generated by the \xten Java backend for
the same program (which was somewhat surprising). 
The reason for the added slowness in the C++ code was because each
typecast from \texttt{Double} to \texttt{Long} involved an explicit check on the
value of the \texttt{Double} type variable to ensure that it lies in the
64-bit range supported by \texttt{Long}, whereas the cast in Java is
handled by a primitive bytecode cast instruction.   However, even in
Java, extraneous casts clearly hurt performance.
%Note that even though
%\texttt{Double} is also 64-bit, the IEEE 754 floating point data format
%allows the actual value of the data stored in \texttt{Double} to be much
%higher(lower) than the maximum(minimum) value supported by
%\texttt{Long}. 

To solve this problem, we designed and implemented the
\emph{IntegerOkay} analysis that identifies variables that can be
safely declared to be of \texttt{Long} type, thus eliminating the need
for costly typecasting on these variables.

\section{Effect on Performance}

To understand the effect on performance caused by typecasting consider a
simple example of \xten code shown in listing \ref{lst:dbl_lng_tc} that just loops
over a 2-dimensional array and sets each element \texttt{A(i,j)} to
\texttt{A(i-1,j-1) + A(i+1, j+1)}.
In this example, the
index variables \texttt{i} and \texttt{j} are declared to be of type
\texttt{Double} and are typecast to \texttt{Long} when used for indexing
into the array.   This example reflects the type of \xten code that we
would generate if we do not have the \emph{IntegerOkay} analysis.

Listing \ref{lst:dbl_lng_notc} shows the same example,
but with \texttt{i} and \texttt{j} declared to be \texttt{Long}, and
thus not requiring an explicit typecast. This example reflects the code
that we would be able to generate with a good \emph{IntegerOkay} analysis.

\begin{lstlisting}[caption={Example for using \texttt{Double} variables for
array indexing},label={lst:dbl_lng_tc},language=x10,numbers=none]
static def useDoubles(scale:Double, n:Long){
  val a: Array_2[Double] = 
    new Array_2[Double](Mix10.rand(scale, scale));
  var i:Double = 0; var j:Double = 0; var v:Long = 0;
  for (v=0;v<n;v++){
    for (j=1;j<a.numElems_2-1;j++){
      for (i=1;i<a.numElems_1-1;i++){
        a(i as Long,j as Long) = a(i as Long -1, j as Long -1) + 
         a(i as Long +1, j as Long +1);
      } } } } 
\end{lstlisting}

\begin{lstlisting}[caption={Example for using \texttt{Long} variables for
indexing},label={lst:dbl_lng_notc},language=x10,numbers=none]
static def useLongs(scale:Double, n:Long){
  val a: Array_2[Double] = 
    new Array_2[Double](Mix10.rand(scale, scale));
  var i:Long = 0; var j:Long = 0; var v:Long = 0;
  for (v=0;v<n;v++){
    for (j=1;j<a.numElems_2-1;j++){
      for (i=1;i<a.numElems_1-1;i++){
        a(i, j) = a(i-1, j-1) + a(i+1, j+1);
      } } } }
\end{lstlisting}

\begin{table}[htbp]
\begin{center}
\input{tables/intok.tex}
\caption{Running times (in seconds) for listings \ref{lst:dbl_lng_tc} and
\ref{lst:dbl_lng_notc}, smaller is better}
\label{tab:intoktable}
\end{center}
\end{table}

Table \ref{tab:intoktable} shows running times (in seconds) for these
two examples for different values of input arguments. For the listing
\ref{lst:dbl_lng_tc}, the C++ code generated by the \xten compiler is
nearly 5 times slower as compared to the Java code generated from \xten for
the same example.  Compared to \ref{lst:dbl_lng_notc} it is slower than
the C++ code for this example by almost 20 times. On the other hand,
Java code for the listing \ref{lst:dbl_lng_tc} is nearly 2 times slower
compared to the Java code for the listing \ref{lst:dbl_lng_notc}.  For
the C++ backend, since the C++ compiler does not provide the checks for
\texttt{Double} to \texttt{Long} typecast, it is implemented in the
\xten C++ backend. For the Java backend, \xten relies on these checks
provided by the JVM.  The more efficient implementation of these checks
in the JVM, compared to that in the \xten C++ backend explains for
comparatively lower slowdowns for the Java code. Section
\ref{sec:intok_perf} gives detailed evaluation of the performance
benefits obtained by using \emph{IntegerOkay} analysis on our benchmark
set.

\section{An Overview of the \emph{IntegerOkay} Analysis}
\label{sec:overview}

In this section we give a high-level overview of how the \emph{IntegerOkay}
analysis works. A detailed algorithm for it is provided in the next section
(section \ref{sec:algo}).
The basic idea behind the \emph{IntegerOkay} analysis is that, for each 
variable \verb|x|, if for every use and every definition of \verb|x| in the
given \matlab function, \verb|x| can be safely assumed to be an integer, i.e. its
declaration as an integer does not change the result of the program,
then it can be declared as an integer. Thus, the problem boils down to
answering the question of whether each use or a definition,
\verb|x| can be safely assumed to be an integer.

There are three possible answers to this question: 
\begin{enumerate}

\item \emph{IntegerOkay}: The variable use/def can be safely assumed to be an
integer.  For example, for a definition like \texttt{x = 2.0} or for use
as an array index like \texttt{A(x)}, it is safe to assume that if
\verb|x| was declared to be an integer, this definition or use will not
affect the result of the program. In other words, for this definition or
use of \verb|x|, \verb|x| is \texttt{IntegerOkay}.

\item \emph{Not IntegerOkay}: The variable cannot be an integer type.
For example consider the expression \texttt{x/y}. Here, since the type
of the operands can affect the result of the division operation, it is
unsafe to assume that \verb|x| and \verb|y| can be of integer type for
this particular use. As another example, consider the definition
\texttt{x = 3.14}. Here, since assuming \verb|x| to be an integer will
result in an error, x is not \emph{IntegerOkay}. 

\item \emph{Conditionally IntegerOkay}: It is possible to have a case where a
variable \verb|x|, for a particular use or def in the function, is an integer
only if some other variable, say \verb|y|, is \emph{IntegerOkay} everywhere
in the given function. In such a case, we say that \verb|x| is
\emph{conditionally IntegerOkay} and \emph{depends} on \verb|y|. 
%The variable \verb|x| can be an integer if for the use or definition in
%question, the variables on which its value depends on, are \emph{IntegerOkay}
%everywhere in the program. 
For example, in a definition like \texttt{x = a+b}, \verb|x| can be an integer
if both \verb|a| and \verb|b| can be integers everywhere in the function. We
say \verb|x| is conditionally \emph{IntegerOkay} and depends on \verb|a| and
\verb|b|. 
%Note that in this particular use of \verb|a| and \verb|b| (as
%operands of the plus operator), since their type does not affect the result
%value of the plus operator, \verb|a| and \verb|b| are \emph{IntegerOkay}.        
Note that these particular uses of \verb|a| and \verb|b| are
\emph{IntegerOkay} because the \texttt{plus()} builtin can be used with
integers safely. However, some other statement may constrain the solution. For
example, a definition of the form \texttt{a = 3.2} somewhere in the function
would mean that \verb|a| is not \emph{IntegerOkay} everywhere and thus
\verb|x| is not \emph{IntegerOkay}.
\end{enumerate}   

In our \mixten compiler we solve the \emph{IntegerOkay} problem using a
simple fixed-point computation.   For each variable use and definition,
the algorithm initially associates it with one of the three abstract
values above.  
We then compute the fixed-point by iteratively refining the dependency lists
of the conditional variables.  Consider each variable $x$, if every use
and definition of $x$ has been determined to be \emph{IntegerOkay}, then
$x$ is removed from the dependency lists of all the variables that are
\emph{Conditionally IntegerOkay} and depend on $x$.  Once the dependency
list for a particular use or definition of a variable is empty, it is
upgraded to be \emph{IntegerOkay} for that particular use or definition.

If a variable is not \emph{IntegerOkay} at some point in the function or
its dependency list does not become empty for some point in the function
(say, for circular dependency), it cannot be declared as an integer.
Since, every time we declare a variable to be integer, one or more
\emph{Conditionally IntegerOkay} variables might be upgraded to
\emph{IntegerOkay}, we iteratively repeat the process of finding
variables that are \emph{IntegerOkay} at all points in the function,
until we reach a fixed point. Note that since we never downgrade a
variable to \emph{Not IntegerOkay} or \emph{Conditionally IntegerOkay},
our iterative algorithm will always terminate. 


\section{The Analysis Algorithm}\label{sec:algo}

The \emph{IntegerOkay} analysis is an intra-procedural, flow-insensitive and
path-insensitive analysis. The basic idea behind identifying whether a
variable can be declared as an integer is that if a variable can safely be an
integer for its every definition and every use in the function, independent of
any other variable's type, then it can be declared to be an integer for the
entire function. It is important that any variable identified as
\emph{IntegerOkay} must be safe to be declared as an integer, thus the
analysis takes a conservative approach and identifies a variable as
\texttt{IntegerOkay} only when it is completely unambiguous. This eliminates
any false-positives (a variable is identified as \texttt{IntegerOkay}, when in
fact it is not \texttt{IntegerOkay}) but may lead to some false-negatives (a
variable is identified not \texttt{IntegerOkay}, when in fact it could be
\texttt{intgerOkay}). For example, if a variable \texttt{i} is used as an
array index variable and also used as an argument to the \texttt{rdivide()}
builtin call somewhere in the function, the analysis identifies it as not
\texttt{IntegerOkay}, even though under the assumption that the function would
execute without any runtime errors, \texttt{i} would be \texttt{IntegerOkay}
(use of a non-integral value as an array index results in a runtime error).       

The input to the analysis is a set of all the double variables in the function,
a set of definitions for each of the variables in this set, and a set of all
the uses for each of the variables in this variable set. The aim is to output a
set of variables that can be safely declared as integers.
%
%Let $V$ be a set of all the variables $v$ that are initially of double type in
%the source \matlab program. Let $D_{v}$ be a set of all the definitions $d$ for
%variable $v$, and $U_{v}$ be a set of all the uses $u$ for variable $v$. 

\subsection{STEP 1 : Initialization}

As mentioned in \secref{sec:overview}, the analysis initializes each
definition and each use of every variable to one of the three abstract values
and assigns a set of dependency variables if the assigned abstract value is
conditionally \emph{IntegerOkay}. 

The analysis represents these three abstract values by the following state
values : \texttt{IntOk}, \texttt{NotIntOk}, and \texttt{CondIntOk} for is
\emph{IntegerOkay}, not \emph{IntegerOkay}, and conditionally \emph{IntegerOkay}
respectively.  Furthermore, let $d.state$ be the state of variable $v$ for
definition $d$ , and $u.state$ be the state of variable $v$ for use $u$. Also,
let $d.deps$ be a set of variables on which the \texttt{CondIntOk} state for
variable $v$ for definition $d$ depends on.  Similarly, let $u.deps$ be a set of
variables on which the \texttt{CondIntOk} state for variable $v$ for use $u$
depends on. The analysis starts with a set of all the double variables $V$ in
the \matlab function, where each variable $v$ has an associated set of its
definitions $D$ and uses $U$. Every $d.state$ and $u.state$ is initialized to
\texttt{NotIntOk} and every $d.deps$ and $u.deps$ is initially set to
$\emptyset$. Algorithm \ref{alg:initialization} gives the algorithm for the
initialization step of the analysis. It checks for every definition and every
use of each variable and assocites an \emph{IntegerOkay} state with each use and
definition. It also assocites a dependency list of variables whose state affects
the state of the variable in question.

 \begin{algorithm}[htbp]
 \caption{Initialization step of the \intok analysis}
\label{alg:initialization}
 \begin{algorithmic}[1]
%\Lcomment{Let $V$ be a set of all the variables in the \matlab function.
\Procedure {Initialize}{$V$}%, $D_{v}$, $U_{v}$}
\Lcomment{Let $V$ be the set of all double variables in the function}
  \Lcomment{Let $v.D$ be the set of all definitions of variable $v$}
  \Lcomment{Let $d.state$ be the integerOkay state of variable $v$ for definition $d$} 
  \Lcomment{Let $v.U$ be the set of all uses of variable $v$}
  \Lcomment{Let $u.state$ be the integerOkay state of variable $v$ for use $u$} 

  \ForAll {$v \in V$}
    \ForAll {$d \in v.D$}
%                \Comment $D$ is a set of all the definitions of $v$ 
      \State $d.state \leftarrow \textsc{GetStateDef}$($v, d$)
%      \If {$d.state = \texttt{CondIntOk}$}
%        \State $d.deps \leftarrow \textsc{GetDepsDef}$($v, d$)
%      \EndIf
    \EndFor
    \ForAll {$u \in v.U$}
%                \Comment $U$ is a set of all the uses of $v$ 
      \State $u.state \leftarrow \textsc{GetStateUse}$($v, u$)
%      \If {$u.state = \texttt{CondIntOk}$}
%        \State $u.deps \leftarrow \textsc{GetDepsUse}$($v, u$)
%      \EndIf
    \EndFor
  \EndFor
\EndProcedure
\Statex
%\Lcomment{Let $v$ be a variable and $d$ be a definition of $v$
\Procedure {GetStateDef}{$v, d$}
\Lcomment{Let $v$ be a variable and $d$ be a definition of $v$}
\Lcomment{Let $d.deps$ be the dependency list of variable $v$ for definition $d$}
\Lcomment{Let $d.RHS$ be the right hand side expression of definition $d$} 
\State 
    \Lcomment{if $d$ is an assignment from a constant}
  \If {$\textsc{IsConstAssignment}$($d$)}
    \If{$\textsc{IsRealInteger}$($d.RHS$)}
      \Lcomment{if the RHS is a real integer}
      \State \textbf{return} \texttt{IntOk}
    \EndIf
  \EndIf  
    \Lcomment{if $d$ is a copy statement}
  \If {$\textsc{IsCopyStmt}$($d$)}
      \Lcomment{add RHS variable (except $v$ itself) to the dependency list of $v$ for $d$}
    \State $d.deps \leftarrow d.deps \cup d.RHS.varName$
      \State $d.deps \leftarrow d.deps - v$
    \State \textbf{return} \texttt{CondIntOk}
  \EndIf
    \Lcomment{if $d$ is an assignment from a call to a builtin function}
  \If {$\textsc{IsAssignmentFromBuiltin}$($d$)}
    \Lcomment{if the RHS builtin always returns integer (eg. floor(), ceil(), etc.)}
    \If {$\textsc{DoesBuiltinReturnInt}$($d.RHS$)}
\algstore{bkbreak}
\end{algorithmic}
\end{algorithm}

 \begin{algorithm}
 %\caption{Initialization step of the \intok analysis - \textsc{GetStateDef}($v, d$)}
\begin{algorithmic}[1]
\algrestore{bkbreak}
      \State \textbf{return} \texttt{IntOk}
    \EndIf
    \Lcomment{if the RHS builtin always returns a double (eg. pi(), etc.)}
    \If {$\textsc{DoesBuiltinReturnDouble}$($d.RHS$)}
      \State \textbf{return} \texttt{NotIntOk}
    \EndIf
    \Lcomment{if the builtin returns integer depending} 
    \Lcomment{on the type of input arguments (eg. plus(), minus(), etc.)}  
    \If {$\textsc{DoesBuiltinReturnIntDepends}$($d.RHS$)}
      \Lcomment{add argumnets (except $v$) to the builtin to the dependency list of $v$ for $d$}
      \State $d.deps \leftarrow d.deps \cup d.RHS.args$
      \State $d.deps \leftarrow d.deps - v$
      \State \textbf{return} \texttt{CondIntOk}
    \EndIf
     \State \textbf{return} \texttt{NotIntOk}
  \EndIf
    \Lcomment{if $d$ is an assignment from an array access}
  \If {$\textsc{IsAssignmentFromArrayAccess}$($d$)}
      \Lcomment{add RHS array variable (except $v$ itself) to the dependency list of $v$ for $d$}
      \State $d.deps \leftarrow d.deps \cup d.RHS.arrayName$
      \State $d.deps \leftarrow d.deps - v$
      \State \textbf{return} \texttt{CondIntOk}
  \EndIf
      \Lcomment{default return \texttt{NotIntOk}}
      \State \textbf{return} \texttt{NotIntOk}
\EndProcedure
\Statex
\Procedure {GetStateUse}{$v, u$}
\Lcomment{Let $v$ be a variable and $u$ be a use expression of $v$}
\Lcomment{Let $u.deps$ be the dependency list of variable $v$ for use $u$}
\Lcomment{if $v$ is used as an array index in $u$}
%\Lcomment{assuming that the use of $v$ as array index is correct in the \matlab
%program}
  \If {$\textsc{IsUseArrayIndex}$($u$)}
    \State \textbf{return} \texttt{IntOk}
  \EndIf
  \Lcomment {if $v$ is used as an argument to a builtin function}
  \If {$\textsc{IsUseBuiltinArgument}$($u$)}
    \Lcomment {if argument type does not affect the correctness of the result
from builtin (eg. plus())}  
    \If {$\textsc{DoesArgTypeAffectResult}$($u$)}
\algstore{bkbreak}
\end{algorithmic}
\end{algorithm}

 \begin{algorithm}
 %\caption{Initialization step of the \intok analysis - \textsc{GetStateDef}($v, d$)}
\begin{algorithmic}[1]
\algrestore{bkbreak}
      \State \textbf{return} \texttt{IntOk}
    \EndIf
    \Lcomment {if the argument type may affect the builtin result (eg. divide())}
    \If {$\textsc{DoesArgTypeAffectResult}$($u$)}
      \State \textbf{return} \texttt{NotIntOk}
    \EndIf
    \Lcomment{if the affect of the argument type depends on the types of other arguments}
    \If {$\textsc{DoesArgTypeDependOnOtherArgs}$($u$)}
      \State $u.deps \leftarrow u.deps \cup u.args$
      \State $u.deps \leftarrow u.deps - v$
      \State \textbf{return} \texttt{CondIntOk}
    \EndIf
  \EndIf
  \Lcomment {if $v$ is used in a copy statement}
  \If {$\textsc{IsUseCopyStatement}$($u$)}
      \State \textbf{return} \texttt{IntOk}
  \EndIf
      \State \textbf{return} \texttt{NotIntOk}
\EndProcedure
 \end{algorithmic}
 \end{algorithm}

%Note that wherever we mark a variable as \texttt{IntOk}, we assume that it is
%being correctly used in the source \matlab function and won't result in a
%runtime error. For instance, if the programmer uses an actual double value, say
%\texttt{i = 3.2}, as an array index, \matlab will result in a runtime error, however, our
%analysis would assume it is correct and report \texttt{i} as \texttt{IntOk}.  
%\begin{description}
%\item[Rules:] The initialization algorithm uses a set of rules to determine the
%state of a variable in a particular definition or use. These rules are also
%used to identify the dependencies if a variable is in \texttt{CondIntOk}
%state.For the definition of a variable, these rules are defined as follows:
%\begin{enumerate}
%\item If the definition is a constant assignment, check the value of the
%constant on RHS. If it is a real integer, the defined variable is
%\texttt{IntOk}.
%\item If the variable is defined in a copy statement, its state is
%\texttt{CondIntOk} and is dependent on the RHS variable. 
%\item If the definition is an assignment to a builtin function call, check
%whether the builtin: (1) always safely returns an integer (eg. floor(), ceil(),
%etc.) - state is \texttt{IntOk}; (2) always returns a double (eg. pi()) - state
%is \texttt{NotIntOk}; (3) safely returns an integer depending on the type of
%input arguments (eg. plus(), minus(), etc.) - state is \texttt{CondIntOk} and
%dependency is all the variables in the input argument except the defined
%variable itself.
%\item If the definition is an assignment to an array access, the state is set
%to \texttt{CondIntOk} and the dependency is the array variable.
%\item For any other case, state is \texttt{NotIntOk}.
%\end{enumerate}  
%For the use of a variable, following are the rules followed:
%\begin{enumerate}
%\item If the variable is used as an array index, its state is set to
%\texttt{IntOk}.
%\item If the variable is used as an argument to a builtin function, such that:
%(1) it's type does not affect the correctness of the result (eg. plus()) - its
%state is set to \texttt{IntOk}; (2) If its type affects the correctness of the
%result (eg. divide()) - its state is set to \texttt{NotIntOk}; 
%\item If the variable is used in a copy statement, its state is \texttt{IntOk}.
%\item For any other case, the state remains as \texttt{NotIntOk}.   
%\end{enumerate}
%\end{description}

%\begin{minipage}{\textwidth}
\begin{algorithm}
\caption{Fixed point solver for the \intok analysis}
\label{alg:fps}
 \begin{algorithmic}[1]

\Procedure {FixedpointSolver}{$V$}
  \Lcomment{Let $V$ be the set of all the double variables in the function}
  \Lcomment{Let $V'$ be the set of variables that can be declared as integers}
  \Lcomment{Let $v.D$ be the set of all definitions of variable $v$}
  \Lcomment{Let $d.state$ be the integerOkay state of variable $v$ for definition $d$} 
  \Lcomment{Let $v.U$ be the set of all uses of variable $v$}
  \Lcomment{Let $u.state$ be the integerOkay state of variable $v$ for use $u$} 
  \Lcomment{Let $v.State$ be the integerOkay state of variable $v$ for the whole function}
  \Lcomment{Let $v.State$ be initialized to $\sim$}
\State $V' \leftarrow \emptyset$
\Repeat
  \State $V'_{old} \leftarrow V'$
\ForAll{$v \in V$}
  \ForAll{$d \in v.D$}
    
    \State $v.State \leftarrow v.State \bowtie d.state$
  \EndFor
  \ForAll{$u \in v.U$}
    \State $v.State \leftarrow v.State \bowtie u.state$
  \EndFor
  \If {$v.State = \texttt{IntOk}$}
    \State $v' \leftarrow v$
    \State $V' \leftarrow V' \cup v'$
    \State $V \leftarrow V - v'$
    \State \textsc{ResolveDependencies}($V, v'$)
  \EndIf 
\EndFor
\State $changed \leftarrow V' \not= V'_{old}$
\Until{$\neg changed$}
\EndProcedure
\Statex
\Procedure{ResolveDependencies}{$V, v'$}
\Lcomment{Let $V$ be the set of all the double variables in the function}
\Lcomment{Let $v'$ be an IntegerOkay variable}
\Lcomment{Let $v.D$ be the set of all definitions of variable $v$}
\Lcomment{Let $d.state$ be the integerOkay state of variable $v$ for definition $d$} 
\Lcomment{Let $d.deps$ be the dependency list of variable $v$ for definition $d$} 
\Lcomment{Let $v.U$ be the set of all uses of variable $v$}
\Lcomment{Let $u.state$ be the integerOkay state of variable $v$ for use $u$} 
\algstore{al2}

\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\algrestore{al2}
\Lcomment{Let $u.deps$ be the dependency list of variable $v$ for use $u$} 
  \ForAll{$v \in V$}
    \ForAll{$d \in v.D$}
      \State $d.deps \leftarrow d.deps - v'$
      \If{$d.deps = \emptyset$}
        \State $d.state \leftarrow \texttt{IntOk}$
      \EndIf
    \EndFor
    \ForAll{$u \in v.U$}
      \State $u.deps \leftarrow u.deps - v'$
      \If{$u.deps = \emptyset$}
        \State $u.state \leftarrow \texttt{IntOk}$
      \EndIf
    \EndFor
  \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}
%\end{minipage}

\subsection{STEP 2: The Fixed Point Solver}

Once the initial state has been assigned for each use and each definition of
every variable in STEP 1, the next step is to find the variables that can be
of integer type across the function. The fixed point solver iteratively finds
these variables until a fixed point is reached and no more variables are safe
to be defined as integers.

The input to the fixed point solver is the set of all double variables $V$ with
state and dependency list initialized for each definition and each use of every
variable $v$ in $V$.
The output of the fixed point solver is $V'$, the set of variables that
can be safely defined as integers. The fixed point solver also defines the variable
$v.State$ that stores the final state value for the variable $v$ in the
function, independent of any use or definition. For each variable $v$,
$v.State$ is assigned an initial empty value $\sim$. $V'$ is initially
set to $\emptyset$.

Algorithm \ref{alg:fps} provides an algorithm for this fixed point solver.
Note that the algorithm uses a $\bowtie$ operator to merge the state values of
various definitions and uses of a variable to obtain its final state. Table
\ref{Tab:merge} gives a definition of the $\bowtie$ operator used by this
analysis. In the table, \texttt{CondIntOk}($s,s=\emptyset$) is the case when
$d.deps \cup u.deps = \emptyset$ for a variable $v$, and
\texttt{CondIntOk}($s,s\ne\emptyset$) 
is the case when $d.deps \cup u.deps \ne \emptyset$.
\begin{table}[b]
\centering
\footnotesize{
\scalebox{0.82}{
\begin{tabular}{|c||c|c|c|c|c|}
\hline
$\bowtie$                        & \texttt{IntOk}    &
\texttt{CondIntOk}($s,s=\emptyset$) & \texttt{CondIntOk}($s,s\ne\emptyset$) &
\texttt{NotIntOk} & $\sim$ \\ \hline \hline
\texttt{IntOk}                   & \texttt{IntOk}    & \texttt{IntOk}
& \texttt{NotIntOk}       & \texttt{NotIntOk}  & \texttt{IntOk} \\ \hline
\texttt{CondIntOk}($s,s=\emptyset$)  & \texttt{IntOk}    & \texttt{IntOk}
& \texttt{NotIntOk}       & \texttt{NotIntOk} & \texttt{CondIntOk}($s,s=\emptyset$) \\ \hline
\texttt{CondIntOk}($s,s\ne\emptyset$) & \texttt{NotIntOk} & \texttt{NotIntOk}
& \texttt{NotIntOk}       & \texttt{NotIntOk} & \texttt{CondIntOk}($s,s\ne\emptyset$) \\ \hline
\texttt{NotIntOk}                & \texttt{NotIntOk} & \texttt{NotIntOk}
& \texttt{NotIntOk}       & \texttt{NotIntOk} & \texttt{NotIntOk} \\ \hline
$\sim$  & \texttt{IntOk}    &
\texttt{CondIntOk}($s,s=\emptyset$) & \texttt{CondIntOk}($s,s\ne\emptyset$) &
\texttt{NotIntOk} & $\sim$ \\ \hline
\end{tabular}
}}
\caption{Definition of the $\bowtie$ merge operator}
\label{Tab:merge}
\end{table}

\pagebreak
\section{An Example}
\begin{minipage}{\textwidth}
Consider the following pseudocode for example:
\begin{verbatim}
/*1*/ x = 3.0;
/*2*/ y = 3.14;
/*3*/ z = x+y;
/*4*/ for (i = 0; i < 5; i++)
/*5*/   y = y+i;
/*6*/ end

\end{verbatim} 

\end{minipage}

In this example, the initialization step proceeds as follows.  On line
1, \verb|x| is \emph{IntegerOkay} since 3.0 is a \emph{real integer}. On
line 2, \verb|y| is  \emph{Not IntegerOkay}. On line 3, \verb|z| is
\emph{Conditionally IntegerOkay} and depends on \verb|x| and \verb|y|,
whereas \verb|x| and \verb|y| are \emph{IntegerOkay} in their use in the
expression \texttt{x+y}.  On line 4, \verb|i| is \emph{IntegerOkay} in
its definition \texttt{i = 0}, in its use in the expression \texttt{i <
5}, and also in the definition \texttt{i++}. On line 5, \verb|y| is
conditionally \emph{IntegerOkay} and depends on \verb|i| in its
definition and it is \emph{IntegerOkay} in its use in \verb|y+i|.
\verb|i| is \emph{IntegerOkay} in its use in \texttt{y+i}. Note that on
line 5, we do not include \verb|y| in its own dependency list, since if
we say, \verb|y| is conditionally \emph{IntegerOkay} and depends on
\verb|y|, it is safe to declare \verb|y| as integer as long as it does
not have any other dependencies and is \emph{IntegerOkay} everywhere
else in the function. 

The fixed-point solver for this example proceeds as follows.  We look
for variables that are \emph{IntegerOkay} at every point in the function.
\verb|x| and \verb|i| are two such variables and we can declare them to
be an integer. We also remove x from the dependency list of definition
of \verb|z| on line 3, and \verb|i| from the dependency list of
definition of \verb|y| on line 5. Next, we search again and find that
\verb|y| is \emph{IntegerOkay} in its use on line 3 and line 5, and also
in its definition on line 5, however it is {\emph{Not IntegerOkay} in
its definition on line 2 and thus it cannot be declared as an integer.
\verb|z| on line 3 is dependent on \verb|y| and thus it can also not be
declared as an integer. At this point, we have reached a fixed point
since there are no more upgrades. Finally, we declare \verb|x| and
\verb|i| as integers, and \verb|y| and \verb|z| as doubles.   
