[pipstransfo.git] / pipstransfo.tex

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

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

\usepackage{listings}
\usepackage{hyperref}


\title{PIPS~--- List of code transformations}



\begin{document}


\chapter{Summary}

\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 removal
\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
\item variable copying
% loop transformations
\item index set splitting
\item loop peeling
\item loop unrolling
\item loop rerolling
\item full loop unrolling
\item idiom recognition
\item unswitching
\item loop fusion
\item loop fission/loop distribution
\item loop normalization
\item unimodular loop transformation/hyperplane method
\item loop interchange
\item loop reversal
\item loop skewing
\item non-unimodular loop transformation
\item strip-mining (loop sectionning)
\item loop coalescing/loop collapsing
\item loop tiling
\item loop parallelization
\item loop vectorization
\item loop invariant code motion
\item software pipelining
\item locality increazing
% inter procedural transformations
\item loop embedding/loop jamming
\item procedure inlining
\item procedure cloning
% basic bloc transformations
\item node splitting
\item forward expression substitution
\item induction variable substitution
\item if-conversion
\item statement reordering
\item expression optimization
\item partial redundancy elimination
% dead code removal
\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{Inter-procedural transformations}

\section{Base blocs transformations}

\section{Dead code removal}




\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[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[common subexpression elimination]{
  is the process of replacing similar expressions by a variable that holds
  the result of their evaluation.}



\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[dead code elimination]{is the process of pruning from a
  function all the statements whose results are
  never used.}

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


\end{document}