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