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