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