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