add template to describe transformer
[pipstransfo.git] / pipstransfo.tex
index 3c0e935..60b8709 100644 (file)
@@ -7,19 +7,79 @@
 
 \usepackage{listings}
 \usepackage{hyperref}
 
 \usepackage{listings}
 \usepackage{hyperref}
+\usepackage{xspace}
+
+\usepackage{makeidx}
+
+\usepackage{etoolbox}
+
+\newcommand{\PIPS}{PIPS\xspace}
+
+% Patch the sectioning commands to provide a hook to be used later
+\preto{\chapter}{\def\leveltitle{\chaptertitle}}
+\preto{\section}{\def\leveltitle{\sectiontitle}}
+\preto{\subsection}{\def\leveltitle{\subsectiontitle}}
+\preto{\subsubsection}{\def\leveltitle{\subsubsectiontitle}}
+
+\makeatletter
+% \@sect is called with normal sectioning commands
+% Argument #8 to \@sect is the title
+% Thus \section{Title} will do \gdef\sectiontitle{Title}
+\pretocmd{\@sect}
+  {\expandafter\gdef\leveltitle{#8}}
+  {}{}
+% \@ssect is called with *-sectioning commands
+% Argument #5 to \@ssect is the title
+\pretocmd{\@ssect}
+  {\expandafter\gdef\leveltitle{#5}}
+  {}{}
+% \@chapter is called by \chapter (without *)
+% Argument #2 to \@chapter is the title
+\pretocmd{\@chapter}
+  {\expandafter\gdef\leveltitle{#2}}
+  {}{}
+% \@schapter is called with \chapter*
+% Argument #1 to \@schapter is the title
+\pretocmd{\@schapter}
+  {\expandafter\gdef\leveltitle{#1}}
+  {}{}
+\makeatother
+
+\newcommand{\PIPSPass}{Pass Name in \PIPS : }
+\newcommand{\PIPSExamples}{Validation folder in \PIPS : }
+\newcommand{\BookRef}{Reference: }
+\newcommand{\NameCommun}[1]{\subsection{#1}\index{\sectiontitle!\subsectiontitle}}
+\newcommand{\NamePipsPass}[1]{\xspace#1\index{\sectiontitle!\subsectiontitle!#1}\xspace}
+
+
+\title{\PIPS~--- List of code transformations}
+
+\makeindex
 
 
+\begin{document}
 
 
-\title{PIPS~--- List of code transformations}
+\chapter{Summary}
 
 
+\section{Section Name}
 
 
+\NameCommun{Commun Transformation Name}
+Description...
 
 
-\begin{document}
+\PIPSPass \NamePipsPass{toto}, \NamePipsPass{toto2}, \NamePipsPass{toto3}
 
 
+\PIPSExamples toto
 
 
-\chapter{Summary}
+\BookRef \cite[p. xxx]{darte_scheduling_2000},
+\cite[p. xxx]{wolfe_high_1996},
+\cite[p. xxx]{zima_supercompilers_1990},
+\cite[p. xxx]{dowd_high_1998},
+\cite[p. xxx]{aho_compilers_2007},
+\cite[p. xxx]{allen_optimizing_2001}
 
 \section{SGuelton}
 
 \section{SGuelton}
+
 \begin{itemize}
 \begin{itemize}
+
 % memory allocation alteration
 \item scalar renaming
 % loop transformations
 % memory allocation alteration
 \item scalar renaming
 % loop transformations
@@ -33,7 +93,7 @@
 \item inlining
 % basic bloc transformations
 \item forward substitution
 \item inlining
 % basic bloc transformations
 \item forward substitution
-% dead code removal
+% dead code elimination
 \item constant propagation
 \item dead code elimination
 
 \item constant propagation
 \item dead code elimination
 
 \item split update operator
 \item statement isolation
 \item strengh reduction
 \item split update operator
 \item statement isolation
 \item strengh reduction
-\end{itemize}
 
 
+\end{itemize}
 
 \section{Teraops}
 
 \section{Teraops}
+
 \begin{itemize}
 \begin{itemize}
+
 % memory allocation alteration
 \item scalar renaming
 \item scalar/array expansion
 \item scalar/array privatization
 % memory allocation alteration
 \item scalar renaming
 \item scalar/array expansion
 \item scalar/array privatization
-\item scalarization
-\item variable copying
+\item scalarization % according to .pdf, not supported by Pips
+\item variable copying % not supported by Pips
 % loop transformations
 % loop transformations
-\item index set splitting
-\item loop peeling
+\item index set splitting % not supported by Pips
+\item loop peeling % not supported by Pips
 \item loop unrolling
 \item loop unrolling
-\item loop rerolling
+\item loop rerolling % not supported by Pips
 \item full loop unrolling
 \item idiom recognition
 \item full loop unrolling
 \item idiom recognition
-\item unswitching
-\item loop fusion
+\item unswitching % not supported by Pips
+\item loop fusion % not supported by Pips
 \item loop fission/loop distribution
 \item loop normalization
 \item unimodular loop transformation/hyperplane method
 \item loop interchange
 \item loop fission/loop distribution
 \item loop normalization
 \item unimodular loop transformation/hyperplane method
 \item loop interchange
-\item loop reversal
+\item loop reversal % not supported by Pips
 \item loop skewing
 \item non-unimodular loop transformation
 \item strip-mining (loop sectionning)
 \item loop skewing
 \item non-unimodular loop transformation
 \item strip-mining (loop sectionning)
-\item loop coalescing/loop collapsing
+\item loop coalescing/loop collapsing % not supported by Pips
 \item loop tiling
 \item loop parallelization
 \item loop tiling
 \item loop parallelization
-\item loop vectorization
+\item loop vectorization % not supported by Pips
 \item loop invariant code motion
 \item loop invariant code motion
-\item software pipelining
+\item software pipelining % not supported by Pips
 \item locality increazing
 \item locality increazing
-% inter procedural transformations
-\item loop embedding/loop jamming
-\item procedure inlining
+% interprocedural transformations
+\item loop embedding/loop jamming % not supported by Pips
+\item procedure inlining % not supported by Pips
 \item procedure cloning
 % basic bloc transformations
 \item node splitting
 \item forward expression substitution
 \item procedure cloning
 % basic bloc transformations
 \item node splitting
 \item forward expression substitution
-\item induction variable substitution
+\item induction variable substitution % not supported by Pips
 \item if-conversion
 \item if-conversion
-\item statement reordering
+\item statement reordering % not supported by Pips
 \item expression optimization
 \item partial redundancy elimination
 \item expression optimization
 \item partial redundancy elimination
-% dead code removal
+% dead code elimination
 \item unreachable code
 \item semantically uneachable code
 \item if and loop elimination
 \item use-def elimination
 \item constant propagation
 \item unreachable code
 \item semantically uneachable code
 \item if and loop elimination
 \item use-def elimination
 \item constant propagation
+
 \end{itemize}
 
 \end{itemize}
 
-\chapter{List of PIPS transformations}
+\chapter{List of \PIPS transformations}
 
 \section{Memory allocation alteration}
 
 \begin{description}
 
 
 \section{Memory allocation alteration}
 
 \begin{description}
 
-\item[scalar renaming]{is the process of renaming scalar variables to
-    suppress false data dependencies.}
+\item[scalar renaming]{is the process of renaming scalar variables to suppress false data dependencies.}
 
 
-\item[privatization]{is the process of detecting variables that are
-    private to a loop body, i.e.\ written first, then read.}
+\item[privatization]{is the process of detecting variables that are private to a loop body, i.e.\ written first, then read.}
 
 \end{description}
 
 
 \end{description}
 
-
 \section{Loop transformations}
 
 \begin{description}
 
 \section{Loop transformations}
 
 \begin{description}
 
-\item[loop unrolling]{
-  is a loop transformation.
-  Unrolling a loop by a factor of $n$ consists in the substitution of a loop
-  body by itself, replicated $n$ times. A prelude and/or postlude are
-  added to preserve the number of iteration.}
+\item[loop unrolling]{is a loop transformation.
+Unrolling a loop by a factor of \(n\) consists in the substitution of a loop body by itself, replicated \(n\) times.
+A prelude and/or postlude are added to preserve the number of iteration.}
 
 
-\item[loop fusion]{
-  is a loop transformation that replaces two loops by a single loops whose
-  body is the concatenation of the bodies of the two initial loops.}
+\item[loop fusion]{is a loop transformation that replaces two loops by a single loops whose body is the concatenation of the bodies of the two initial loops.}
 
 
-\item[loop tiling]{
-  is a loop nest transformation that changes the loop execution order
-  through a partitions of the iteration space into
-  chunks, so that the iteration is performed over each chunk and in the
-  chunks.}
+\item[loop tiling]{is a loop nest transformation that changes the loop execution order through a partitions of the iteration space into chunks, so that the iteration is performed over each chunk and in the chunks.}
 
 
-\item[loop interchange]{is a loop transformation that permutes two
-  loops from a loop nest.}
+\item[loop interchange]{is a loop transformation that permutes two loops from a loop nest.}
 
 
-\item[loop unswitching]{is a loop transformation that replaces a
-  loop containing a test independent from the loop execution by a test
-  containing the loop without the test in both true and false branch.}
+\item[loop unswitching]{is a loop transformation that replaces a loop containing a test independent from the loop execution by a test containing the loop without the test in both true and false branch.}
 
 
-\item[loop normalization]{is a loop transformation that changes
-  the loop initial increment value or the loop range to enforce certain values,
-  generally~1.}
+\item[loop normalization]{is a loop transformation that changes the loop initial increment value or the loop range to enforce certain values, generally~1.}
 
 \end{description}
 
 
 \end{description}
 
-\section{Inter-procedural transformations}
+\section{Interprocedural transformations}
 
 \section{Base blocs transformations}
 
 
 \section{Base blocs transformations}
 
-\section{Dead code removal}
-
-
-
+\section{Dead code elimination}
 
 \begin{description}
 
 
 \begin{description}
 
+\item[dead code elimination]{is the process of pruning from a function all the statements whose results are never used.}
 
 
-\item[inlining]{
-  is a function transformation. Inlining a function
-  \texttt{foo} in its caller \texttt{bar} consists in the substitution
-  of the calls to \texttt{foo} in \texttt{bar} by the function body
-  after replacement of the formal parameters by their effective
-  parameters.
-}
-
-\item[forward substitution]{
-  is the process of replacing a reference read in an
-  expression by the latest expression affected to it.}
-
+\item[common subexpression elimination]{is the process of replacing similar expressions by a variable that holds the result of their evaluation.}
 
 
+\item[goto elimination]{is the process of replacing \texttt{goto} instructions by a hierarchical control flow graph.}
 
 
+\end{description}
 
 
+\section{Other (unclassified)}
 
 
-\item[reduction detection]{
-  is an analysis that identifies statements that perform a reduction over a
-  variable.}
-
-\item[parallelism detection]{
-  is a common name for analysis that detect if a loop can be run in parallel.}
-
-\item[parallelism extraction]{
-  is a common name for code transformations that modifies loop nest to make it legal to
-  run them in parallel.}
-
-\item[directive generation]{
-  is a common name for code transformations that annotate the code with directives.}
+\begin{description}
 
 
-\item[constant propagation]{
-  is a pass that replaces a variable by its value when this value is
-  known at compile time.}
+\item[inlining]{is a function transformation.
+Inlining a function \texttt{foo} in its caller \texttt{bar} consists in the substitution of the calls to \texttt{foo} in \texttt{bar} by the function body after replacement of the formal parameters by their effective parameters.}
 
 
-\item[instruction selection]{
-  is the process of mapping parts of the IR to machine instructions.}
+\item[forward substitution]{is the process of replacing a reference read in an expression by the latest expression affected to it.}
 
 
-\item[goto elimination]{
-  is the process of replacing \texttt{goto} instructions by a hierarchical control flow
-  graph.}
-\item[outlining]{
-  is the process of extracting part of a function body into a new function
-  and replacing it in the initial function by a function call.}
+\item[reduction detection]{is an analysis that identifies statements that perform a reduction over a variable.}
 
 
-\item[common subexpression elimination]{
-  is the process of replacing similar expressions by a variable that holds
-  the result of their evaluation.}
+\item[parallelism detection]{is a common name for analysis that detect if a loop can be run in parallel.}
 
 
+\item[parallelism extraction]{is a common name for code transformations that modifies loop nest to make it legal to run them in parallel.}
 
 
+\item[directive generation]{is a common name for code transformations that annotate the code with directives.}
 
 
-\item[statement isolation]{is the process of replacing all
-  variables referenced in a statement by newly declared variables. A
-  prologue
-  and an epilogue are added to copy old variable values to new variable, back
-  and forth.}
+\item[constant propagation]{is a pass that replaces a variable by its value when this value is known at compile time.}
 
 
-\item[dead code elimination]{is the process of pruning from a
-  function all the statements whose results are
-  never used.}
+\item[instruction selection]{is the process of mapping parts of the IR to machine instructions.}
 
 
-\item[array linearization]{is the process of converting
-  multidimensional array into unidimensional arrays, possibly with a
-  conversion from array to pointer.}
+\item[outlining]{is the process of extracting part of a function body into a new function and replacing it in the initial function by a function call.}
 
 
+\item[statement isolation]{is the process of replacing all variables referenced in a statement by newly declared variables.
+A prologue and an epilogue are added to copy old variable values to new variable, back and forth.}
 
 
-\item[iteration clamping]{is a loop transformation that extends
-  the loop range but guards the loop body with the former range.}
+\item[array linearization]{is the process of converting multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.}
 
 
-\item[flatten code]{is the process of pruning a function body from
-  declaration blocks so that all declarations are made at the top level.}
+\item[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.}
 
 
-\item[strength reduction]{is the process of replacing an operation
-  by an operation of lower cost.}
+\item[flatten code]{is the process of pruning a function body from declaration blocks so that all declarations are made at the top level.}
 
 
-\item[split update operator]{is the process of replacing an update
-  operator by its expanded form.}
+\item[strength reduction]{is the process of replacing an operation by an operation of lower cost.}
 
 
-\item[n address code generation]{is the process of splitting
-  complex expression in simpler ones that take at most $n$ operands.}
+\item[split update operator]{is the process of replacing an update operator by its expanded form.}
 
 
-\item[memory footprint reduction]{is the process of tiling a loop
-  to make sure the iteration over the tile has a memory footprint bounded by
-  a given value.}
+\item[n address code generation]{is the process of splitting complex expression in simpler ones that take at most \(n\) operands.}
 
 
-\item[redundant load-store elimination]{is an inter procedural transformation
-  that optimizes data transfers by delaying and merging them.}
+\item[memory footprint reduction]{is the process of tiling a loop to make sure the iteration over the tile has a memory footprint bounded by a given value.}
 
 
-\item[invariant code motion]{is a loop transformation that moves outside
-  of the loop
-  the code from its body that is independent from the iteration.}
+\item[redundant load-store elimination]{is an inter procedural transformation that optimizes data transfers by delaying and merging them.}
 
 
+\item[invariant code motion]{is a loop transformation that moves outside of the loop the code from its body that is independent from the iteration.}
 
 
+\item[loop rerolling]{finds manually unrolled loop and replace them by their non-unrolled version.}
 
 
-\item[loop rerolling]{finds manually unrolled loop and replace
-  them by their non-unrolled version.}
 \end{description}
 
 \end{description}
 
-
 \nocite{*}
 \bibliographystyle{alpha}
 \nocite{*}
 \bibliographystyle{alpha}
-\bibliography{refs}
+\bibliography{\jobname}
 
 
+\printindex
 
 \end{document}
 
 \end{document}