pipstransfo.tex

   1 \documentclass[pdftex, a4paper, 11pt]{report}
   2
   3 \usepackage[utf8]{inputenc}
   4 \usepackage[T1]{fontenc}
   5 \usepackage[english]{babel}
   6 \usepackage{lmodern}
   7
   8 \usepackage{listings}
   9 \usepackage{hyperref}
  10 \usepackage{xspace}
  11
  12 \usepackage{makeidx}
  13
  14 \usepackage{etoolbox}
  15
  16 \newcommand{\PIPS}{PIPS\xspace}
  17
  18 % Patch the sectioning commands to provide a hook to be used later
  19 \preto{\chapter}{\def\leveltitle{\chaptertitle}}
  20 \preto{\section}{\def\leveltitle{\sectiontitle}}
  21 \preto{\subsection}{\def\leveltitle{\subsectiontitle}}
  22 \preto{\subsubsection}{\def\leveltitle{\subsubsectiontitle}}
  23
  24 \makeatletter
  25 % \@sect is called with normal sectioning commands
  26 % Argument #8 to \@sect is the title
  27 % Thus \section{Title} will do \gdef\sectiontitle{Title}
  28 \pretocmd{\@sect}
  29   {\expandafter\gdef\leveltitle{#8}}
  30   {}{}
  31 % \@ssect is called with *-sectioning commands
  32 % Argument #5 to \@ssect is the title
  33 \pretocmd{\@ssect}
  34   {\expandafter\gdef\leveltitle{#5}}
  35   {}{}
  36 % \@chapter is called by \chapter (without *)
  37 % Argument #2 to \@chapter is the title
  38 \pretocmd{\@chapter}
  39   {\expandafter\gdef\leveltitle{#2}}
  40   {}{}
  41 % \@schapter is called with \chapter*
  42 % Argument #1 to \@schapter is the title
  43 \pretocmd{\@schapter}
  44   {\expandafter\gdef\leveltitle{#1}}
  45   {}{}
  46 \makeatother
  47
  48 \newcommand{\PIPSPass}{Pass Name in \PIPS : }
  49 \newcommand{\PIPSExamples}{Validation folder in \PIPS : }
  50 \newcommand{\BookRef}{Reference: }
  51 \newcommand{\NameCommun}[1]{\subsection{#1}\index{\sectiontitle!\subsectiontitle}}
  52 \newcommand{\NamePipsPass}[1]{\xspace#1\index{\sectiontitle!\subsectiontitle!#1}\xspace}
  53
  54
  55 \title{\PIPS~--- List of code transformations}
  56
  57 \makeindex
  58
  59 \begin{document}
  60
  61 \chapter{Summary}
  62
  63 \section{Section Name}
  64
  65 \NameCommun{Commun Transformation Name}
  66 Description...
  67
  68 \PIPSPass \NamePipsPass{toto}, \NamePipsPass{toto2}, \NamePipsPass{toto3}
  69
  70 \PIPSExamples toto
  71
  72 \BookRef \cite[p. xxx]{darte_scheduling_2000},
  73 \cite[p. xxx]{wolfe_high_1996},
  74 \cite[p. xxx]{zima_supercompilers_1990},
  75 \cite[p. xxx]{dowd_high_1998},
  76 \cite[p. xxx]{aho_compilers_2007},
  77 \cite[p. xxx]{allen_optimizing_2001}
  78
  79 \section{SGuelton}
  80
  81 \begin{itemize}
  82
  83 % memory allocation alteration
  84 \item scalar renaming
  85 % loop transformations
  86 \item loop unrolling
  87 \item loop fusion
  88 \item loop tiling
  89 \item loop rerolling
  90 \item loop interchange
  91 \item loop normalization
  92 % inter procedural transformations
  93 \item inlining
  94 % basic bloc transformations
  95 \item forward substitution
  96 % dead code elimination
  97 \item constant propagation
  98 \item dead code elimination
  99
 100 % ??
 101 \item array linearization
 102 \item common subexpression elimination
 103 \item directive generation
 104 \item flatten code
 105 \item goto elimination
 106 \item instruction selection
 107 \item invariant code motion
 108 \item iteration clamping
 109 \item loop unswitching
 110 \item memory footprint reduction
 111 \item n adress code generation
 112 \item outlining
 113 \item parallelism detection
 114 \item parallelism extraction
 115 \item privatization
 116 \item reduction detection
 117 \item redundant load-store elimination
 118 \item split update operator
 119 \item statement isolation
 120 \item strengh reduction
 121
 122 \end{itemize}
 123
 124 \section{Teraops}
 125
 126 \begin{itemize}
 127
 128 % memory allocation alteration
 129 \item scalar renaming
 130 \item scalar/array expansion
 131 \item scalar/array privatization
 132 \item scalarization % according to .pdf, not supported by Pips
 133 \item variable copying % not supported by Pips
 134 % loop transformations
 135 \item index set splitting % not supported by Pips
 136 \item loop peeling % not supported by Pips
 137 \item loop unrolling
 138 \item loop rerolling % not supported by Pips
 139 \item full loop unrolling
 140 \item idiom recognition
 141 \item unswitching % not supported by Pips
 142 \item loop fusion % not supported by Pips
 143 \item loop fission/loop distribution
 144 \item loop normalization
 145 \item unimodular loop transformation/hyperplane method
 146 \item loop interchange
 147 \item loop reversal % not supported by Pips
 148 \item loop skewing
 149 \item non-unimodular loop transformation
 150 \item strip-mining (loop sectionning)
 151 \item loop coalescing/loop collapsing % not supported by Pips
 152 \item loop tiling
 153 \item loop parallelization
 154 \item loop vectorization % not supported by Pips
 155 \item loop invariant code motion
 156 \item software pipelining % not supported by Pips
 157 \item locality increazing
 158 % interprocedural transformations
 159 \item loop embedding/loop jamming % not supported by Pips
 160 \item procedure inlining % not supported by Pips
 161 \item procedure cloning
 162 % basic bloc transformations
 163 \item node splitting
 164 \item forward expression substitution
 165 \item induction variable substitution % not supported by Pips
 166 \item if-conversion
 167 \item statement reordering % not supported by Pips
 168 \item expression optimization
 169 \item partial redundancy elimination
 170 % dead code elimination
 171 \item unreachable code
 172 \item semantically uneachable code
 173 \item if and loop elimination
 174 \item use-def elimination
 175 \item constant propagation
 176
 177 \end{itemize}
 178
 179 \chapter{List of \PIPS transformations}
 180
 181 \section{Memory allocation alteration}
 182
 183 \begin{description}
 184
 185 \item[scalar renaming]{is the process of renaming scalar variables to suppress false data dependencies.}
 186
 187 \item[privatization]{is the process of detecting variables that are private to a loop body, i.e.\ written first, then read.}
 188
 189 \end{description}
 190
 191 \section{Loop transformations}
 192
 193 \begin{description}
 194
 195 \item[loop unrolling]{is a loop transformation.
 196 Unrolling a loop by a factor of \(n\) consists in the substitution of a loop body by itself, replicated \(n\) times.
 197 A prelude and/or postlude are added to preserve the number of iteration.}
 198
 199 \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.}
 200
 201 \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.}
 202
 203 \item[loop interchange]{is a loop transformation that permutes two loops from a loop nest.}
 204
 205 \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.}
 206
 207 \item[loop normalization]{is a loop transformation that changes the loop initial increment value or the loop range to enforce certain values, generally~1.}
 208
 209 \end{description}
 210
 211 \section{Interprocedural transformations}
 212
 213 \section{Base blocs transformations}
 214
 215 \section{Dead code elimination}
 216
 217 \begin{description}
 218
 219 \item[dead code elimination]{is the process of pruning from a function all the statements whose results are never used.}
 220
 221 \item[common subexpression elimination]{is the process of replacing similar expressions by a variable that holds the result of their evaluation.}
 222
 223 \item[goto elimination]{is the process of replacing \texttt{goto} instructions by a hierarchical control flow graph.}
 224
 225 \end{description}
 226
 227 \section{Other (unclassified)}
 228
 229 \begin{description}
 230
 231 \item[inlining]{is a function transformation.
 232 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.}
 233
 234 \item[forward substitution]{is the process of replacing a reference read in an expression by the latest expression affected to it.}
 235
 236 \item[reduction detection]{is an analysis that identifies statements that perform a reduction over a variable.}
 237
 238 \item[parallelism detection]{is a common name for analysis that detect if a loop can be run in parallel.}
 239
 240 \item[parallelism extraction]{is a common name for code transformations that modifies loop nest to make it legal to run them in parallel.}
 241
 242 \item[directive generation]{is a common name for code transformations that annotate the code with directives.}
 243
 244 \item[constant propagation]{is a pass that replaces a variable by its value when this value is known at compile time.}
 245
 246 \item[instruction selection]{is the process of mapping parts of the IR to machine instructions.}
 247
 248 \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.}
 249
 250 \item[statement isolation]{is the process of replacing all variables referenced in a statement by newly declared variables.
 251 A prologue and an epilogue are added to copy old variable values to new variable, back and forth.}
 252
 253 \item[array linearization]{is the process of converting multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.}
 254
 255 \item[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.}
 256
 257 \item[flatten code]{is the process of pruning a function body from declaration blocks so that all declarations are made at the top level.}
 258
 259 \item[strength reduction]{is the process of replacing an operation by an operation of lower cost.}
 260
 261 \item[split update operator]{is the process of replacing an update operator by its expanded form.}
 262
 263 \item[n address code generation]{is the process of splitting complex expression in simpler ones that take at most \(n\) operands.}
 264
 265 \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.}
 266
 267 \item[redundant load-store elimination]{is an inter procedural transformation that optimizes data transfers by delaying and merging them.}
 268
 269 \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.}
 270
 271 \item[loop rerolling]{finds manually unrolled loop and replace them by their non-unrolled version.}
 272
 273 \end{description}
 274
 275 \nocite{*}
 276 \bibliographystyle{alpha}
 277 \bibliography{\jobname}
 278
 279 \printindex
 280
 281 \end{document}