X-Git-Url: https://scm.cri.mines-paristech.fr/git/pipstransfo.git/blobdiff_plain/3906dede2abec0ff63d7fa33abfeabc743a537ef..6e28a30da02870e986ad5ad2130b66153b5239df:/pipstransfo.tex?ds=inline diff --git a/pipstransfo.tex b/pipstransfo.tex index 7a6bbcb..f24434a 100644 --- a/pipstransfo.tex +++ b/pipstransfo.tex @@ -3,24 +3,167 @@ \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} +\usepackage{lmodern} \usepackage{listings} \usepackage{hyperref} +\usepackage{xspace} +\def\PIPS{PIPS\xspace} -\title{PIPS~--- List of code transformations} + +\title{\PIPS~--- List of code transformations} \begin{document} -\chapter{List of Pips transformations} +\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} @@ -31,10 +174,7 @@ \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[inlining]{ is a function transformation. Inlining a function @@ -48,15 +188,9 @@ is the process of replacing a reference read in an expression by the latest expression affected to it.} -\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[reduction detection]{ is an analysis that identifies statements that perform a reduction over a @@ -90,12 +224,7 @@ is the process of replacing similar expressions by a variable that holds the result of their evaluation.} -\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[statement isolation]{is the process of replacing all variables referenced in a statement by newly declared variables. A @@ -111,11 +240,6 @@ multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.} -\item[privatization]{is the process of detecting variables that - are private to a loop body, i.e.\ written first, then read.} - -\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[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.} @@ -149,4 +273,10 @@ them by their non-unrolled version.} \end{description} + +\nocite{*} +\bibliographystyle{alpha} +\bibliography{refs} + + \end{document}