The core of the \matlab Tamer is the {\em value analysis}. It's an
extensible monolithic context-sensitive inter-procedural forward
propagation of abstract \matlab values. For every program point, it estimates
what possible values every variable can take on. Most notably it finds
the possible set of mclasses. It also propagates function handle
values. This allows resolution of all possible call edges, and the
construction of a complete call graph of a tame \matlab program.

The value analysis is part of an extensible interprocedural analysis
framework. It contains a set of modules, one building on top of the
other. All of them can be used by users of the framework to build analyses.

\begin{itemize}

\item The \textbf{abstract value analysis} (section \ref{sec:value}), built
using the interprocedural analysis framework, is a generic analysis of abstract
\matlab values. The implementation is agnostic to the actual representation of
abstract values, but is aware of \matlab mclasses. It can thus build a
callgraph using the correct function lookup semantics including function
specialization.

\item We provide an implementation of \textbf{composite values} like cell
arrays, structures and function handles, which is generic in the
implementation of abstract matrix values
(section \ref{sec:composite}). This makes composite values completely
transparent, allowing users to implement very fine-grained abstract value
analyses by only providing an abstraction for \matlab values which are
matrices.

\item Building on top of all the above modules and putting everything
together, we provide an abstraction for all \matlab values, which we
call simple values (section \ref{sec:simple}). Since it includes the
function handle abstractions, this can be used by users to build a
complete tame \matlab callgraph. This is the \textbf{concrete value
analysis}, whose results are presented in section \ref{sec:results}.
\end{itemize}

\begin{comment}
The analysis is meant to be modular with respect to the abstraction of
values, so that the machinery of the analysis can be reused. This
allows more powerful, fine-grained value analyses, while only
requiring the specification of the new value abstraction and how they
behave with respect to indexing operations and Matlab builtin
functions. The builtin framework helps with the latter specification.

Any value abstraction must include the mclass of the estimated
value. The mclass is required because the Matlab function look-up
semantics depend on the mclass of arguments, due to the mclass
specialization semantics. Value abstractions that do not estimate
function handle values will result in missing call edges.

We provide an implementation of a value abstraction, which includes estimation
of function handle values, cell array values and structure
values. This abstraction can be used to build a complete call graph.

In the following section we will introduce our context-sensitive
interprocedural analysis framework, a high-level view of the value
analysis, and the specific value abstraction that is used to construct
complete callgraphs.}
\end{comment}


\section{Introducing the Value Analysis}
\label{sec:value}

The abstract value analysis is a forward propagation of generic
abstract \matlab values. The mclass of any abstract value is always
known.

A specific instance of a value analysis may use different
representations for values of different mclasses. For example,
function handle values may be represented in a different way than
numeric values. This in turn means that values of different Matlab
classes can not be merged (joined).

\subsection{Mclasses, Values and Value Sets:}

To define the value analysis independently of a specific
representation of values, 
We first define the set of all mclasses:
\begin{equation*}
C = \{ \text{\tt double},\text{\tt single},\text{\tt logical},\text{\tt cell},\ldots \}
\end{equation*}
For each mclass, we need some lattice of values that represent estimations of \matlab values of that class:
\begin{equation*}
V_{mclass} = \{v: v \text{ represents a \matlab value with mclass } mclass \}, mclass \in C
\end{equation*}
We require that merge operations are defined, so
$\forall v_1, v_2 \in V_{mclass}, v_1 \wedge v_2 \in V_{mclass}.$

%we call the set of all possible values $V_C$:
%\begin{equation*}
%V_C = \underset{mc \in C}{\cup} V_{mc}
%\end{equation*}

We can not join values of different mclasses, because their actual
representation may be incompatible. 
%So $V_C$ is not a lattice. 
In order to allow union values for variables, i.e. to allow variables to
have more than one possible mclass, we estimate the value of a \matlab
variable as a set of pairs of abstract values and their mclasses,
where the mclasses are disjoint. We call this a value set. More
formally, we define a value set as:
\begin{align*} 
ValueSet = \{&(mclass_1,v_1),(mclass_2,v_2),\ldots,(mclass_n,v_n):\\
&class_i \neq class_j, class_i \in C, v_i \in V_{class_i}\}
\end{align*}
Or the set of all possible value sets given a set $V$ of lattices for every mclass.
\begin{align*}
S_V = \{\{(mclass_k,v_k): mclass_i \neq mclass_j, v_i \in V_{mclass_i}, k \in 0..n\} : 0 \leq n \leq |C|\} \}
\end{align*}
%\begin{align*}
%S(V_C) &= \bigprod_{mclass \in C} (V_{mclass} \times \{mclass\} \cup )) \}
%\end{align*}
This is a lattice, with the join operation
%\begin{align*}
%s_1 \wedge s_2 =& \{(mclass,v) : (mclass,v) \in s_1, (mclass,v) \notin s_2\} \\
%  \cup &\{(mclass,v) : (mclass,v) \notin s_1, (mclass,v) \in s_2\} \\
%  \cup &\{(mclass,v_1 \wedge v_2) : (mclass,v_1) \in s_1, (mclass,v_2) \in s_2\}
%\end{align*}
which is the simple set union of all the pairs, but for any two pairs
with matching mclasses, their values get joined, resulting in only one pair in the result set.

While the notion of a value set allows the analysis to deal with
ambiguous variables, still building a complete callgraph and giving a
valid estimation of types, having ambiguous variables is not conducive
to code generation for a language like {\sc FORTRAN}. So\\
\centerline{{\tt if (...); t = 4; else; t = 'hi'; end} }
results in $t$ having the abstract value $\{({\text{\tt
double}},4), ({\text{\tt char}},{\text{\tt 'hi'}})\}$. This example
is not tame \matlab.

\subsection{Flow Sets:} We define a flow set as a set of pairs of variables and value sets, i.e.
\begin{equation*}
flow = \{(var_1,s_1),(var_2,s_2),...,(var_n,s_n) : s_i \in S_V, var_i \neq var_j\}
\end{equation*}
and we define an associated look-up operation
\begin{equation*}
 flow(var) = s \text{ if } (var,s) \in flow
\end{equation*}
This is a lattice whose merge operation resembles that of the value sets.

Flow sets may be $nonviable$, representing non-reachable code (for
statements after errors, or non-viable branches). Joining any
non-$bottom$ flow set with the $nonviable$ set results in the viable
flow \rednote{ set, joining} $bottom$ and $nonviable$ results in $nonviable$.

\subsection{Argument and Return sets:}

The context or argument set for the interprocedural analysis is a
vector of values representing argument values. Arguments are not value
sets, but simple values $v \in V_c$ with a single known mclass $c$. When encountering
a call, the analysis has to construct all combinations of possible argument
sets, construct a context from that and analyze the call for all
such contexts. For example, if we reach a call
{\tt r = foo(a,b)}, with a flow set
\begin{equation*}
\{(a,\{(\text{{\tt double}},v_1),(\text{{\tt char}},v_2)\}\rednote{)},(b,\{(\text{{\tt logical}},v_3)\})\},
\end{equation*}
the value analysis constructs two contexts, from $(v_1,v_3)$ and $(v_2,v_3)$,
and analyzes function {\tt foo} with each context. Note how the
dominant argument for the first context is {\tt double}, whereas it is
{\tt char} for the second. If there exist mclass specialized versions
for {\tt foo}, then this results in call edges to, and analysis
of, two different functions.

More formally, for a call $     func$($a_1$, $a_2$, $\cdots$ ,
$a_n$) at program point $p$, with the input flow set $f_p$, we
have the set of all possible contexts
\begin{align*}
allargs =& f_p(a_1) \times f_p(a_2) \times \cdots \times f_p(a_n) =  \prod_{1 \leq i \leq n} {f_p(a_i)}
\end{align*}

the interprocedural analysis needs to analyze $func$ with all these contexts and merge the result,

\begin{equation*}
 R = \bigwedge_{arg \in allargs} analyze(func, arg)
\end{equation*}

To construct a context, the value analysis may simplify (push up)
values to a more general representation. For example, if the value
abstraction includes constants, the push up operation may turn
constants into $top$. Otherwise, the number of contexts for any given
function may grow unnecessarily large.

The result of analyzing a function with an argument set is a vector of
value sets, where every component represents a returned variable. They are joined by
component-wise joining of the value sets. In the value analysis we
require that for a particular call, the number of returned variables
is the same for all possible contexts.

\subsection{Builtin Propagators:}

Every implementation of the value abstractions needs to provide a
builtin propagator, which provides flow equations for builtins. If $B$
is the set of all defined builtin functions $\{ {\text{\tt plus}},
{\text{\tt minus}}, {\text{\tt sin}}, \ldots \}$, then the builtin
propagator $P_V$ for some representation of values $V_C$ is a function
 mapping a builtin and argument set to a result set.
\begin{equation*}
  P_V : B \times \bigcup_{n \in \mathbb{N}} V^n \rightarrow \bigcup_{n \in \mathbb{N}} (S_V)^n
\end{equation*}
The builtin framework provides tools to help implement builtin
propagators by providing builtin visitor classes. The framework also
provides attributes for builtin functions, for example the class
propagation information attributes.

\section{Flow Equations}

In the following subsection we will show a sample of flow equations to illustrate
the flow analysis. We assume a statement to be at program point
$p$, with incoming flow set $f_p$. The flow equation for program point $p$
results in the new flow set $f_p'$

\begin{itemize}
\item {\tt $var_t$ = $var_s$}: \hspace{.5cm}
$ f_p' = f_p \setminus \{(var_t,f_p(var_t))\} \cup \{(var,f_p(var_s))\}$
\item {\tt $var$ = $l$}, where $l$ is a literal with mclass $c_l$ and value representation $v_l$:

\begin{equation*}
f_p' = f_p \setminus \{(var,f_p(var))\} \cup \{(var,\{(c_l,v_l)\})\}
\end{equation*}
\item {\tt [$t_1$,$t_2$,$\ldots$,$t_m$] = $func$($a_1$,$a_2$,$\ldots$,$a_n$)}, a function call to some function $func$:
\\
with

\begin{equation*}
call_{func,arg} =
\left\{
    \begin{array}{ll}
       P_V(b, args)        & \mbox{if $func$ with $args$ refers to a builtin $b$} \\
       analyze(f, args) & \mbox{if $func$ with $args$ refers to a function $f$}
    \end{array}
\right.
\end{equation*}
we set

\begin{equation*}
R = \bigwedge_{args \in f_p(a_1) \times f_p(a_2) \times \cdots \times f_p(a_n)  } call_{func,args}
\end{equation*}
then

\begin{equation*}
f_p' = f_p \setminus \bigcup_{i = 1}^m \{ (t_i,f_p(t_i))\} \cup \bigcup_{i = 1}^m \{(t_i,R_i)\}
\end{equation*}
\end{itemize}


Note that when analyzing a call to a function in an m-file, the argument values will be
pushed up. For calls to builtins, the actual argument values will be
used, effectively in-lining the behavior of builtin functions.

\section{Structures, Cell Arrays and Function Handles}
\label{sec:composite}
We implemented a value abstraction for structs, cell arrays and
function handles \rednote{(internally called {\tt AggrValue})}. 
This abstraction is again modular, this one with
respect to the representation of matrix values (i.e. values with
mclass {\tt double}, {\tt single}, {\tt char}, {\tt logical} or
\rednote{one of the integer mclasses}). Structures, cell arrays and function handles act as
containers for other values, making them effectively transparent.  A
user may provide a fine-grained abstraction for just matrix values and
combine it with \rednote{the} abstraction of composite values to implement a
concrete value analysis.

\subsection{{\tt struct}, {\tt cell}:}
For structures and cell arrays, there are two possible abstractions:

\begin{itemize}
  \item \emph{tuple}: The exact index set of the {\tt struct}/{\tt
  cell} is known and every indexing operation can be completely
  resolved statically. Then the value is represented as a set of
  pairs $ \{(i_1, s_1), (i_2, s_2),..,(i_n, s_n) : i_k \in I, s_n \in
  S_V\} $, where I is an index set - integer vectors for cell
  arrays, and names for structs.

  \item \emph{collection}: Not all indexing operations can be
  statically resolved, or the set of indices is unknown. In this case,
  all value sets contained in the struct or cell are merged
  together, and the representation is a single value set $s \in S_V$.
\end{itemize}
The usual representation for a structure is a tuple, because
usually all accesses (dot-expressions) are explicit in the code and
known. Cell arrays are usually a collection, because the index
expressions are usually not constant. But cell arrays tend to have
homogeneous mclass values, so there is some expectation that any
access of a {\tt struct} or {\tt cell} results in some unambiguous
mclass and thus allows static compilation.

\subsection{{\tt function\_handle}:}
As explained in section \ref{sec:lambda}, function handles can be
created either by referring to an existing function, or by using a
lambda expression to generate an anonymous function using a lambda
expression. The lambda simplification (presented in
section \ref{sec:lsimp}) reduces lambda expressions to single calls.

We model all function handles as sets of function handle pairs. A
function handle pair consists of a reference to a function and a
vector of partial argument value sets. A function handle value may
thus refer to multiple possible function/partial argument pairs. 

Given some flow set $f_p$ defined at the program point $p$,

%\begin {itemize}

%\item 
%\hspace{.5cm}
{\tt g = @sin} results in \hspace{.3cm}\\
\centerline{ $f_p' = f_p \setminus {(g,f_p(g))} \cup \{(g, \{(\text{\tt function\_handle},\{({\text {\tt sin}}, ())\})\})\} $}
%\item 
%\hspace{.5cm}
{\tt g = @(t,y) lambda1(D,c,t,y)} results in\\
      \centerline{ $f_p' = f_p \setminus {(g,f_p(g))} \cup \{(g, \{(\text{\tt function\_handle},\{({\text {\tt lambda1}}, (f_p(D), f_p(c)))\}) \})\}$}
%\end{itemize}

Note that function handles get invoked at array get statements, rather
than calls. That is because the tame IR is constructed without mclass
information, and will correctly interpret a function handle as a
variable. When the target of an array get statement is a function
handle, the analysis inserts one or more call edges at that program
point, referring to the functions contained in the function
handle.
%The partial arguments contained in the function handle get
%combined with the index variables of the array get statement, and all
%possible combinations of functions and arguments get analyzed.

\section{The Simple Matrix Abstraction}
\label{sec:simple}

Using the value abstraction for structures, cell arrays and function,
we implemented a concrete value abstraction by adding an abstraction
for matrix values, which we call simple matrix values. On top of the
required mclass, this abstraction merely adds constant propagation for
scalar doubles, strings (char vectors), and scalar logicals.

This allows the analysis of \matlab code utilizing optional function
arguments using the builtin function {\tt nargin}, and some limited
dynamic features utilizing strings. For example, a call like {\tt
ones(n,m,'int8')} can be considered tame.

This implementation represents the concrete value analysis that is
used to construct complete callgraphs.

%\subsection{Example}
%example showing 
%lambda propagation
%multiple contexts


