<commit_before>\chapter{Optimizations on intermediate representation}

\section{Static single assignment form}

While not an optimization in itself, static single assignment (SSA)
form is a prerequisite for many optimization techniques, which is why
we describe it here. 

In their conference paper from 2013
\cite{Braun:2013:SEC:2450247.2450258}, Braun et al present an
algorithm capable of a direct translation of abstract syntax trees to
SSA form.  We do not use it here, because we have not been able to
couple it with our compilation context which seems to require
compilation from the end to the beginning of the program. 

Instead, we use the traditional technique based on \emph{iterated
  dominance frontiers}.

Muchnick \cite{Muchnick:1998:ACD:286076} discusses SSA form, but the
description is very sketchy.  He describes using iterated dominance
frontiers to find nodes where $\phi$ functions must be inserted, but
he does not discuss how to rename variables.  He also does not justify
why the start node of the control flow graph is included in the
argument to each computation using iterated dominance frontiers.  His
notation is essentially the same as that of Cytron et al
\cite{Cytron:1991:ECS:115372.115320}.  For these reasons, we base our
description on the paper by Cytron et al, rather than on Muchnick's
book.

SSA form is a per-variable property.  Some optimizations are possible
even if not every variable has this property, so that some variables
are assigned multiple times.  In order for a variable $V$ to respect
the SSA property, a $\phi$ function for $V$ is required in control
flow node $Z$ whenever there are control flow nodes $X$ and $Y$
containing assignments to $V$, $X \ne Y$, $X \rightarrow^+ Z$, $Y
\rightarrow^+ Z$.  The node $Z$ is called a \emph{join point} for $V$.
Since adding a $\phi$ function in $Z$ introduces an assignment to $V$,
$Z$ must then recursively be considered in order to find other join
points requiring additional $\phi$ functions.  The concept of a join
point is more generally defined for an arbitrary set of control flow
nodes $S$.  The set of join points $J(S)$ is defined as the set of all
nodes $Z$ such that there are two non-null paths starting from two
distinct nodes $X$ and $Y$ in S and converge in $Z$.  The
\emph{iterated join} $J^+(S)$ is defined as the limit of the
increasing sets of nodes $J_1(S) = J(S)$, $J_{i+1}(S) = J(S \cup
J_i(S))$.

Consider the control flow graph in \refFig{fig-ssa-join-1}.  Empty
boxes contain neither assignments nor references to the variable
\texttt{x}.  There are three nodes containing assignments to
\texttt{x}, namely B, C, and D.  The set $J^+(\{B, C, D\}) = \{E\}$.

\begin{figure}
\begin{center}
\inputfig{fig-ssa-join-1.pdf_t}
\end{center}
\caption{\label{fig-ssa-join-1}
Example of join point.}
\end{figure}

Now, to compute the nodes where a $\phi$ function is required, Cytron
et al use the concept of \emph{iterated dominance frontier}.  First,
the dominance frontier of a single node $x$, written $DF(x)$ is the
set of nodes $y$ such that $x$ dominates an immediate predecessor of
$y$ but $x$ does not strictly dominate $y$.  The dominance frontier of
a \emph{set} of nodes $S$ is the natural extension of $DF$ to a set,
namely the union of the vales for each element.  The iterated
dominance frontier is defined in a way similar to the iterated join. 
$DF^+(S)$ is defined as the limit of the
increasing sets of nodes $DF_1(S) = DF(S)$, $DF_{i+1}(S) = DF(S \cup
DF_i(S))$.

Consider again the control flow graph in \refFig{fig-ssa-join-1}.  The
set $DF^+(\{B, C, D\}) = \{E, F\}$.  Note that this set includes the
node $F$ which is not a join point for the nodes that assign to $x$.
This discrepancy is clearly indicated in the the paper by Cytron et
al.  If we analyze it a bit more, we see that clearly no $\phi$
function is required in $F$.  The method using iterated dominance
frontiers thus computes more nodes than required.  

However, notice that if \refFig{fig-ssa-join-1} represents a \cl{}
program, then the node $F$ could not contain a reference to
\texttt{x}, simply because no \cl{} construct allows the creation of
an uninitialized lexical variable.  Therefore, in $F$, the variable
\texttt{x} must be \emph{dead}.  The situation in
\refFig{fig-ssa-join-1} can be quite common in \cl{} because variables
often have very limited scope.  It is therefore desirable to avoid
considering the node $F$ as needing a $\phi$ function.

Now consider the control flow graph in \refFig{fig-ssa-join-2}.  The
only difference from \refFig{fig-ssa-join-1} is that node $E$ does not
contain a use of the variable \texttt{x}.

\begin{figure}
\begin{center}
\inputfig{fig-ssa-join-2.pdf_t}
\end{center}
\caption{\label{fig-ssa-join-2}
Example of join point.}
\end{figure}

Clearly, the node $E$ is in the set $J^+(\{B, C, D\})$, even though
the variable \texttt{x} is dead in $E$.  Hence, it is not sufficient
to consider an algorithm based directly on join sets rather than on
iterated dominance frontiers in order to avoid including nodes where
variables are dead.   However, checking variable liveness before
including a node in the calculation of the iterated dominance frontier
should take care of problems generated by both the situation
illustrated by \refFig{fig-ssa-join-1} and by \refFig{fig-ssa-join-2}.<commit_msg>Included citation of Lengauer and Tarjan.<commit_after>\chapter{Optimizations on intermediate representation}

\section{Static single assignment form}

While not an optimization in itself, static single assignment (SSA)
form is a prerequisite for many optimization techniques, which is why
we describe it here. 

In their conference paper from 2013
\cite{Braun:2013:SEC:2450247.2450258}, Braun et al present an
algorithm capable of a direct translation of abstract syntax trees to
SSA form.  We do not use it here, because we have not been able to
couple it with our compilation context which seems to require
compilation from the end to the beginning of the program. 

Instead, we use the traditional technique based on \emph{iterated
  dominance frontiers}.

Muchnick \cite{Muchnick:1998:ACD:286076} discusses SSA form, but the
description is very sketchy.  He describes using iterated dominance
frontiers to find nodes where $\phi$ functions must be inserted, but
he does not discuss how to rename variables.  He also does not justify
why the start node of the control flow graph is included in the
argument to each computation using iterated dominance frontiers.  His
notation is essentially the same as that of Cytron et al
\cite{Cytron:1991:ECS:115372.115320}.  For these reasons, we base our
description on the paper by Cytron et al, rather than on Muchnick's
book.

SSA form is a per-variable property.  Some optimizations are possible
even if not every variable has this property, so that some variables
are assigned multiple times.  In order for a variable $V$ to respect
the SSA property, a $\phi$ function for $V$ is required in control
flow node $Z$ whenever there are control flow nodes $X$ and $Y$
containing assignments to $V$, $X \ne Y$, $X \rightarrow^+ Z$, $Y
\rightarrow^+ Z$.  The node $Z$ is called a \emph{join point} for $V$.
Since adding a $\phi$ function in $Z$ introduces an assignment to $V$,
$Z$ must then recursively be considered in order to find other join
points requiring additional $\phi$ functions.  The concept of a join
point is more generally defined for an arbitrary set of control flow
nodes $S$.  The set of join points $J(S)$ is defined as the set of all
nodes $Z$ such that there are two non-null paths starting from two
distinct nodes $X$ and $Y$ in S and converge in $Z$.  The
\emph{iterated join} $J^+(S)$ is defined as the limit of the
increasing sets of nodes $J_1(S) = J(S)$, $J_{i+1}(S) = J(S \cup
J_i(S))$.

Consider the control flow graph in \refFig{fig-ssa-join-1}.  Empty
boxes contain neither assignments nor references to the variable
\texttt{x}.  There are three nodes containing assignments to
\texttt{x}, namely B, C, and D.  The set $J^+(\{B, C, D\}) = \{E\}$.

\begin{figure}
\begin{center}
\inputfig{fig-ssa-join-1.pdf_t}
\end{center}
\caption{\label{fig-ssa-join-1}
Example of join point.}
\end{figure}

Now, to compute the nodes where a $\phi$ function is required, Cytron
et al use the concept of \emph{iterated dominance frontier}.  First,
the dominance frontier of a single node $x$, written $DF(x)$ is the
set of nodes $y$ such that $x$ dominates an immediate predecessor of
$y$ but $x$ does not strictly dominate $y$.  The dominance frontier of
a \emph{set} of nodes $S$ is the natural extension of $DF$ to a set,
namely the union of the vales for each element.  The iterated
dominance frontier is defined in a way similar to the iterated join. 
$DF^+(S)$ is defined as the limit of the
increasing sets of nodes $DF_1(S) = DF(S)$, $DF_{i+1}(S) = DF(S \cup
DF_i(S))$.

Consider again the control flow graph in \refFig{fig-ssa-join-1}.  The
set $DF^+(\{B, C, D\}) = \{E, F\}$.  Note that this set includes the
node $F$ which is not a join point for the nodes that assign to $x$.
This discrepancy is clearly indicated in the the paper by Cytron et
al.  If we analyze it a bit more, we see that clearly no $\phi$
function is required in $F$.  The method using iterated dominance
frontiers thus computes more nodes than required.  

However, notice that if \refFig{fig-ssa-join-1} represents a \cl{}
program, then the node $F$ could not contain a reference to
\texttt{x}, simply because no \cl{} construct allows the creation of
an uninitialized lexical variable.  Therefore, in $F$, the variable
\texttt{x} must be \emph{dead}.  The situation in
\refFig{fig-ssa-join-1} can be quite common in \cl{} because variables
often have very limited scope.  It is therefore desirable to avoid
considering the node $F$ as needing a $\phi$ function.

Now consider the control flow graph in \refFig{fig-ssa-join-2}.  The
only difference from \refFig{fig-ssa-join-1} is that node $E$ does not
contain a use of the variable \texttt{x}.

\begin{figure}
\begin{center}
\inputfig{fig-ssa-join-2.pdf_t}
\end{center}
\caption{\label{fig-ssa-join-2}
Example of join point.}
\end{figure}

Clearly, the node $E$ is in the set $J^+(\{B, C, D\})$, even though
the variable \texttt{x} is dead in $E$.  Hence, it is not sufficient
to consider an algorithm based directly on join sets rather than on
iterated dominance frontiers in order to avoid including nodes where
variables are dead.   However, checking variable liveness before
including a node in the calculation of the iterated dominance frontier
should take care of problems generated by both the situation
illustrated by \refFig{fig-ssa-join-1} and by \refFig{fig-ssa-join-2}.

To compute the immediate dominator of every node in the flow graph, we
use the algorithm by Langauer and Tarjan
\cite{Lengauer:1979:FAF:357062.357071}. 
{'fraction_non_alphanumeric': 0.0869805075395366, 'fraction_numerical': 0.013240161824200073, 'mean_word_length': 4.272418807561803, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '928106', 'n_tokens_mistral': 3345, 'n_tokens_neox': 3146, 'n_words': 1649}