\documentclass[pdftex, a4paper, 11pt]{report}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{lmodern}

\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}

\chapter{Summary}

\section{Section Name}

\NameCommun{Commun Transformation Name}
Description...

\PIPSPass \NamePipsPass{toto}, \NamePipsPass{toto2}, \NamePipsPass{toto3}

\PIPSExamples toto

\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}

\begin{itemize}

% memory allocation alteration
\item scalar renaming
% loop transformations
\item loop unrolling
\item loop fusion
\item loop tiling
\item loop rerolling
\item loop interchange
\item loop normalization
% inter procedural transformations
\item inlining
% basic bloc transformations
\item forward substitution
% dead code elimination
\item constant propagation
\item dead code elimination

% ??
\item array linearization
\item common subexpression elimination
\item directive generation
\item flatten code
\item goto elimination
\item instruction selection
\item invariant code motion
\item iteration clamping
\item loop unswitching
\item memory footprint reduction
\item n adress code generation
\item outlining
\item parallelism detection
\item parallelism extraction
\item privatization
\item reduction detection
\item redundant load-store elimination
\item split update operator
\item statement isolation
\item strengh reduction

\end{itemize}

\section{Teraops}

\begin{itemize}

% memory allocation alteration
\item scalar renaming
\item scalar/array expansion
\item scalar/array privatization
\item scalarization % according to .pdf, not supported by Pips
\item variable copying % not supported by Pips
% loop transformations
\item index set splitting % not supported by Pips
\item loop peeling % not supported by Pips
\item loop unrolling
\item loop rerolling % not supported by Pips
\item full loop unrolling
\item idiom recognition
\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 reversal % not supported by Pips
\item loop skewing
\item non-unimodular loop transformation
\item strip-mining (loop sectionning)
\item loop coalescing/loop collapsing % not supported by Pips
\item loop tiling
\item loop parallelization
\item loop vectorization % not supported by Pips
\item loop invariant code motion
\item software pipelining % not supported by Pips
\item locality increazing
% 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 induction variable substitution % not supported by Pips
\item if-conversion
\item statement reordering % not supported by Pips
\item expression optimization
\item partial redundancy elimination
% dead code elimination
\item unreachable code
\item semantically uneachable code
\item if and loop elimination
\item use-def elimination
\item constant propagation

\end{itemize}

\chapter{List of \PIPS transformations}

\section{Memory allocation alteration}

\begin{description}

\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.}

\end{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 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 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 normalization]{is a loop transformation that changes the loop initial increment value or the loop range to enforce certain values, generally~1.}

\end{description}

\section{Interprocedural transformations}

\section{Base blocs transformations}

\section{Dead code elimination}

\begin{description}

\item[dead code elimination]{is the process of pruning from a function all the statements whose results are never used.}

\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)}

\begin{description}

\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[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.}

\item[constant propagation]{is a pass that replaces a variable by its value when this value is known at compile time.}

\item[instruction selection]{is the process of mapping parts of the IR to machine instructions.}

\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[array linearization]{is the process of converting multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.}

\item[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.}

\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[strength reduction]{is the process of replacing an operation by an operation of lower cost.}

\item[split update operator]{is the process of replacing an update operator by its expanded form.}

\item[n address code generation]{is the process of splitting complex expression in simpler ones that take at most \(n\) operands.}

\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[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.}

\end{description}

\nocite{*}
\bibliographystyle{alpha}
\bibliography{\jobname}

\printindex

\end{document}