\input{defines.tex}
\documentstyle{article}

\newcommand{\merge}{\mbox{merge}}
\newcommand{\range}{\mbox{range}}

\title{Range Checking via Extended Static Single Assignment Form}

\author{Thomas Colthurst}

\begin{document}
\maketitle

\section{Introduction}

%Compiler optimization is not one of the fields traditionally associated
%with constraint programming.  None the less, the two fields are related:
%constraint languages need fast optimizing compilers, and optimizing compilers
%can use many of the techniques of constraint programming.  This paper looks
%at perhaps one of the simplest examples of this dual association, range
%checking.

The problem of range checking, from the compiler's point of view, is to 
determine the possible range of values of every variable at every point
in the program, and to use this information to remove checks for array
bounds, remove dead code, issue diagnostics, etc.  It is a generalization
of the optimization known as constant propagation.
%From the point of view of constraint programming,
%the compiler is manipulating partial information about the data flow of
%the program.  As you will see, the algorithm the compiler uses monotonically
%increases the partial information through the lattice of possible ranges.

Range checking is a relatively old compiler optimization technique 
\cite{harrison:old}.
This paper presents a new algorithm for the optimization, using an 
extended version of the Static Single Assignment data structure pionered
by Mark Wegman and Kenneth Zadeck \cite{zadeck:cytron} for data flow analysis.
 
\section{Range Propagation}

The first step in designing an algorithm to perform range checking is
to decide which compiler data types are to be range checked.  The compiler
might reasonably, say, decide to range check integer, floating point,
boolean\footnote{Range checking booleans is the same as constant
propagating them, but if you are adding range checking to your compiler
you might reasonably remove constant propagation as redundant.},
pointer and character data types, while ignoring array, string, or other
more complicated types.  The ranged representation of these data types is
typically a pair of the data type, denoted [low,high], representing the
fact that the variable x is between low and high, or $\mbox{low} \leq x \leq 
\mbox{high} $.
For data types like integers or floating point numbers which are typically
thought of representing an unbound range, we add the symbols $+ \infinity$ and
$- \infinity$ to the data type, with the rule 
$- \infinity \leq x \leq + \infinity$ for all $x$.
Further, for data types like floating point numbers, our 
the ranged representation should be able to distinguish between the possibilities of
$\mbox{low} < x < \mbox{high}$, $\mbox{low} \leq x < \mbox{high}$, 
$\mbox{low} < x \leq \mbox{high}$, and $\mbox{low} \leq x \leq \mbox{high}$.
This can either be done by tacking on two bits to the representation, or
representing $\mbox{low} < x$ as $\mbox{low} - \epsilon \leq x$ 
where $\epsilon$ is the
granularity of the machine's internal representation of the floating point
number.  The first option is more machine portable, while the second is
easier to code.

The set of possible ranges of a data type forms a lattice with respect
to inclusion, with BOTTOM being the null range which doesn't contain
anything and TOP = $[-\infinity, +\infinity]$ the range which contains
all values.  The reason for
this geometric language is Figure 1, which shows how we ``descend'' down 
the lattice of inclusion as we monotonically increase our knowledge
of a range.

\begin{figure}
\vspace{4.0 in}
\special{psfile=lattice.ps}
\caption{The Range Inclusion Lattice}
\end{figure}
 
The next step is to implement ranged versions of
all the primitive operations on these data types.  For instance, the compiler
must be able to determine that $ [a,b] + [c,d] = [e+f,b+d] $ for integers
and floating points (and to determine the correct $<$ versus $\leq$
interpretation for floating point numbers).  Other
operations such as multiplication are more complicated, due to the
complication of sign changes; for example,
$$ [a,b] * [c,d] = [ \min( a*c, a*d, b*c, b*d ), \max( a*c, a*d, b*c, b*d ) ]$$ 
Other operations, such as the bitwise xor of two integers, are so complicated
from the point of view of ranges as to be not worth implementing exactly
(though it does make an interesting challenge to come up with an algorithm
that performs it exactly).
 
As will be shown in the section on Test Pushing, it will also be necessary
to perform the inverses of the primitive operations on ranges.  That is to
say that we must be able to determine that $[a,b] = [x+c,y+d]$ if we know that
$[x,y] = [a,b] - [c,d]$.  This operation would be called
{\tt left-minus-inverse}, while {\tt right-minus-inverse([c,d],[x,y])
= [a-x, b-y]}.
Again, for some operations, the inverse will be
too complicated to be worth implementing.

Finally, for any non-primitive operation, such as a function call, we
assume the worse and have it return TOP.

\section{SSA Form and Range Merging}

Our goal is to determine the range of every variable at every point of
the program.  At first glance, this would seem to involve storing a
range for every variable for every statement in the program, which would
take far too much memory for any real world compiler to do.  Instead,
we use a smarter strategy:  we only determine the ranges of variables
at the points where the variable could possibly change.  And the data
structure which keeps track of this is called Single Static Assignment
form \cite{zadeck:cytron}.

Here is how SSA form works:  Variables change values at assignments.
At each
assignment, we add new ``SSA'' variables to the program, so that each
variable has but one assignment (hence the name, Single Assignment).
Figure 2 shows a program fragment in which the variable i is assigned
to four times.  Figure 3 shows the program fragment in SSA form: we have
replaced the variable i with the four variables $i_1$, $i_2$, $i_3$, and $i_4$,
and changed the references to i with references to the appropriate
new SSA variable. 

\begin{figure}
\begin{verbatim}
i = 5; 
i = 9 + i; 
if ( j > 10 ) 
  i = 12 + i;  
else 
  i = 3 - i; 
endif 
j = i; 
\end{verbatim}
 
\caption{``The initial program fragment''}
 
\end{figure}
 
\begin{figure}
\begin{verbatim}
i_1 = 5; 
i_2 = 9 + i_1; 
if ( j > 10 ) 
  i_3 = 12 + i_2; 
else 
  i_4 = 3 - i_2; 
endif 
j = i_?; 
\end{verbatim}
\caption{ ``The program fragment in SSA Form (almost)''}
\end{figure}

But wait!  Which SSA variable should we use in the final assignment  
to j?  We have no knowledge of which branch the program will take --
it might take both at the different times for all we know -- so we
cannot tell whether use $i_3$ or $i_4$.  To remedy this situation, we add
a new SSA variable $i_5$ at the merge point after the if-then-else (a merge point is, in general, a
statement which can have more than one possible previous statement) and
define it to be equal to the merge of $i_3$ and $i_4$ (see Figure 4).  Now
this {\tt merge} function (called a $\phi$-function in the SSA literature)
isn't a real function -- it is not executed at run-time and the compiler
does not omit code for it. 
All it does is allow us to model the program data flow in such
a way that every variable use has an unique assignment.  

\begin{figure}
\begin{verbatim}
i_1 = 5; 
i_2 = 9 + i_1; 
if ( j > 10 ) 
  i_3 = 12 + i_2;
else 
  i_4 = 3 - i_2; 
endif 
i_5 = merge(i_3, i_4);
j = i_5; 
\end{verbatim}
\caption{``The program fragment in SSA Form (finally)''}
\end{figure}

%In particular,
%if we store the source code location of every variable's (unique)
%assignment in that variable's symbol table entry, it becomes easy to
%calculate ``def-use chains''. 

It is clear how to fit SSA form into a range-checking algorithm.  We
keep a range for every SSA variable, and we take the merge of two
ranges to be their ``union''; 
{\tt merge}$([a,b],[c,d]) = [\min(a,c), \max(b,d)]$. 

%We should also note that SSA form has many uses in compiler optimization
%besides just range-checking (constant propagation and the assignment
%of variables to registers, to name just two), so go out and put SSA form
%into your compiler today. 

\section{Split Points and Extended SSA Form} 

So far we have been discussing places in a program where a variable
can change its value.  What we really want to model, however, is where
a variable's range can change.  Besides merge points, there is one other
control flow feature which can cause a variable's range to change:  split
points (statements like if's or until's, after which there is more than
one possible next statement).  For example, in Figure 4, if we knew that
$j$ was somewhere in the range $[1,20]$ before the if statement, then we would
know that $j$ would have the range $[11,20]$ at $i_3$'s assignment, and 
the range [1,10] at $i_4$'s assignment.

To model this knowledge, we need to do three things.  First, we
assume that the source code has been transformed into three address form
and that new boolean variables have been added so that every split
point is of the form \begin{tt}if ( b == TRUE )\end{tt}.
Second, after every such split point we add a statement of the form
\begin{tt}$b_t$ = split( TRUE );\end{tt} to the top of the if block and a
\begin{tt}$b_f$ = split( FALSE );\end{tt} statement to to top of the 
corresponding else block.  The split function has no effect on range
calculations; it just marks the assignment as a dummy statement for which
the compiler should not emit code. 
 
Finally, the range of every variable which is used in the definition
of {\tt t} must be recalculated.  The recalculation takes place by 
inserting the assignment of new SSA variables to an {\tt intersect} function.
The {\tt intersect} function is similar to the {\tt merge} function
but calculates the intersection of the two passed ranges rather than
the union:  {\tt merge}$([a,b],[c,d]) = [\max(a,c), \min(b,d)]$ if
$\max(a,c) \leq \min(b,d)$ and BOTTOM otherwise.  If a variable 
{\tt i} is used in the definition of a split boolean 
{\tt b = f( i, j );} (where {\tt f} is a primitive operation), 
then {\tt i}'s range in the if block can be calculated as
{\tt $i_1$ = intersect( i, left-f-inverse( $b_t$, j ) );} 
 
We are almost done -- almost.  As the program fragment in Figure 6
demonstrates, once we have recalculated the range of the variable
{\tt b}, we have new knowledge about (and thus need to recalculate)
the ranges of the variables
in its definition (in this case, {\tt a}) and uses
({\tt c}).  Variables in the definition generate
{\tt intersect-inverse} statements of the appropriate variety, while
variables that use the recalculated variable in their definitions
generate {\tt split} functions.  In both cases, we must recurse on
the new variables and generate variables for all of their uses
and definition, and so on until everything in the transitive
closure of use and definition has been reached. 

This all may seem like a lot of extra work.  Please note that
in practice you only have to generate {\tt split} or {\tt intersect} functions
for variables that are used before control flow rejoins.
Specifically, if there is no code between (i.e., in the control flow) 
all of a variable's
{\tt split} functions and the subsequent {\tt merge} function, then all
of the said {\tt split} functions and the {\tt merge} function may be
removed.  Further, if you are prepared to do use conservative propagation
algorithm and don't mind not getting the best possible analysis, any or 
all {\tt split} and {\tt intersect} statements can be thrown out, as they
only add information.  In a production compiler, for instance, it might
be a good idea to generate no more than some large constant number of
{\tt split} and {\tt intersect} statements, as it is certainly possible
in the worst case for an exponential number of them to be generated,
compared to the size of the original code.

We call a program with {\tt split} and {\tt intersect} 
functions at the proper places to be in
Extended SSA Form.  (This is not to be confused with modified SSA Form,
another variant of SSA Form sometimes used in value numbering optimiziation
algorithms).

\begin{figure}
\begin{verbatim}
i_1 = 5;
i_2 = 9 + i_1;
t = j_1 > 10;
if ( t == TRUE )
  t_1 = split( TRUE );
  j_2 = intersect( j_1, left->-inverse( t_1, 10 ) );
  i_3 = 12 + i_2;
else
  t_2 = split( FALSE );	
  j_3 = intersect( j_1, left->-inverse( t_2, 10 ) );
  i_4 = 3 - i_2;
endif
j_4 = merge(j_2, j_3);
i_5 = merge(i_3, i_4);
j_5 = i_5;
\end{verbatim}

\caption{``The program fragment in Extended SSA Form''}
\end{figure}

\begin{figure}
\begin{verbatim}
b = a + 5;
c = b - 10;
if ( b > 10 )
  print a, b, c;
endif
\end{verbatim}
\caption{``Another program fragment''}
\end{figure}

\begin{figure}
\begin{verbatim}
b_1 = a_1 + 5;
c_1 = b_1 - 10;
t = b_1 > 10;
if ( t )
   t_1 = split( TRUE );
   b_2 = intersect( b_1, left->-inverse( t_1, 10 ) );
   a_2 = intersect( a_1, left-+-inverse( b_1, 5 ) );
   c_2 = split(  b_2 - 10 );
   print a_2, b_2, c_2; 
endif
\end{verbatim}
\caption{``Split and Range Functions''}
\end{figure}

%\section{Bounding the Lattice}

%There is one last problem to solve before we have a range-checking
%algorithm.
 
\section{The Algorithms}

We present the range checking algorithm in two parts:  first, an algorithm
to transform a program into Extended SSA form, and second, an algorithm to
perform range checking on a program in Extended SSA form.  Both algorithms
are adapted from the putting a program into SSA form and constant propagation
algorithm from \cite{zadeck:cytron}. 

{\bf Algorithm 1: Conversion to ESSA Form }

{\bf Input:}  The program, already broken up into basic blocks and
put into three address form.

\begin{enumerate}

\item Go through the entire program, and for variable keep a list  
of the places where it is used (the use-list) and defined (the def-list).

\item 

\end{enumerate}

{\bf Algorithm 2}

(Algorithm 2 assumes the existence of a worklist data structure.
When assignments are put on the worklist, the worklist automatically
orders them in topological order so that the top of the worklist is
the earliest assignment.)

\begin{enumerate}

\item Initialize all ranges to Top

\item Put every assignment on the worklist

\item While the worklist is not empty,
   evaluate its top assignment.
   If this evaluation changes the range of the variable,
   put all of the variable's uses on the worklist.
 
\item Repeat step 3 until the worklist is empty.
 
\end{enumerate}
 
%\section{The Applications}

%\section{Conclusion}

%The author would like to thank Kenneth Zadeck for his comments on this
%algorithm.

\begin{thebibliography}{Barnsley 99}

\bibitem[Harrison 77]{harrison:old}
Harrison, William H.  {\em Compiler Analysis of the Value Ranges for Variables.}
IEEE Transactions on Software Engineering, Vol. Se-3, No. 3, May 1977.

\bibitem[Cytron 91]{zadeck:cytron}
Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, and Kenneth
Zadeck.  Efficiently computing static single assignment form and the
control dependence graph.  {\it ACM Transactions on Programming Languages
and Systems}, 13(4):451-490, October 1991.

\bibitem[Zadeck 94]{zadeck:book} Frances Allen, Bary K. Rosen, 
and F. Kenneth Zadeck, editors.
{\em Optimization in Compilers}.  Addison Wesley/ACM Press, 1993.

\end{thebibliography}

\end{document}