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 \title{\PIPS~--- List of code transformations}
  15
  16 \begin{document}
  17
  18 \chapter{Summary}
  19
  20 \section{SGuelton}
  21
  22 \begin{itemize}
  23
  24 % memory allocation alteration
  25 \item scalar renaming
  26 % loop transformations
  27 \item loop unrolling
  28 \item loop fusion
  29 \item loop tiling
  30 \item loop rerolling
  31 \item loop interchange
  32 \item loop normalization
  33 % inter procedural transformations
  34 \item inlining
  35 % basic bloc transformations
  36 \item forward substitution
  37 % dead code removal
  38 \item constant propagation
  39 \item dead code elimination
  40
  41 % ??
  42 \item array linearization
  43 \item common subexpression elimination
  44 \item directive generation
  45 \item flatten code
  46 \item goto elimination
  47 \item instruction selection
  48 \item invariant code motion
  49 \item iteration clamping
  50 \item loop unswitching
  51 \item memory footprint reduction
  52 \item n adress code generation
  53 \item outlining
  54 \item parallelism detection
  55 \item parallelism extraction
  56 \item privatization
  57 \item reduction detection
  58 \item redundant load-store elimination
  59 \item split update operator
  60 \item statement isolation
  61 \item strengh reduction
  62
  63 \end{itemize}
  64
  65 \section{Teraops}
  66
  67 \begin{itemize}
  68
  69 % memory allocation alteration
  70 \item scalar renaming
  71 \item scalar/array expansion
  72 \item scalar/array privatization
  73 \item scalarization % according to .pdf, not supported by Pips
  74 \item variable copying % not supported by Pips
  75 % loop transformations
  76 \item index set splitting % not supported by Pips
  77 \item loop peeling % not supported by Pips
  78 \item loop unrolling
  79 \item loop rerolling % not supported by Pips
  80 \item full loop unrolling
  81 \item idiom recognition
  82 \item unswitching % not supported by Pips
  83 \item loop fusion % not supported by Pips
  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 % not supported by Pips
  89 \item loop skewing
  90 \item non-unimodular loop transformation
  91 \item strip-mining (loop sectionning)
  92 \item loop coalescing/loop collapsing % not supported by Pips
  93 \item loop tiling
  94 \item loop parallelization
  95 \item loop vectorization % not supported by Pips
  96 \item loop invariant code motion
  97 \item software pipelining % not supported by Pips
  98 \item locality increazing
  99 % interprocedural transformations
 100 \item loop embedding/loop jamming % not supported by Pips
 101 \item procedure inlining % not supported by Pips
 102 \item procedure cloning
 103 % basic bloc transformations
 104 \item node splitting
 105 \item forward expression substitution
 106 \item induction variable substitution % not supported by Pips
 107 \item if-conversion
 108 \item statement reordering % not supported by Pips
 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
 118 \end{itemize}
 119
 120 \chapter{List of \PIPS transformations}
 121
 122 \section{Memory allocation alteration}
 123
 124 \begin{description}
 125
 126 \item[scalar renaming]{is the process of renaming scalar variables to suppress false data dependencies.}
 127
 128 \item[privatization]{is the process of detecting variables that are private to a loop body, i.e.\ written first, then read.}
 129
 130 \end{description}
 131
 132 \section{Loop transformations}
 133
 134 \begin{description}
 135
 136 \item[loop unrolling]{is a loop transformation.
 137 Unrolling a loop by a factor of \(n\) consists in the substitution of a loop body by itself, replicated \(n\) times.
 138 A prelude and/or postlude are added to preserve the number of iteration.}
 139
 140 \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.}
 141
 142 \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.}
 143
 144 \item[loop interchange]{is a loop transformation that permutes two loops from a loop nest.}
 145
 146 \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.}
 147
 148 \item[loop normalization]{is a loop transformation that changes the loop initial increment value or the loop range to enforce certain values, generally~1.}
 149
 150 \end{description}
 151
 152 \section{Interprocedural transformations}
 153
 154 \section{Base blocs transformations}
 155
 156 \section{Dead code removal}
 157
 158 \begin{description}
 159
 160 \item[dead code elimination]{is the process of pruning from a function all the statements whose results are never used.}
 161
 162 \item[common subexpression elimination]{is the process of replacing similar expressions by a variable that holds the result of their evaluation.}
 163
 164 \item[goto elimination]{is the process of replacing \texttt{goto} instructions by a hierarchical control flow graph.}
 165
 166 \end{description}
 167
 168 \section{Other (non classes)}
 169
 170 \begin{description}
 171
 172 \item[inlining]{is a function transformation.
 173 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.}
 174
 175 \item[forward substitution]{is the process of replacing a reference read in an expression by the latest expression affected to it.}
 176
 177 \item[reduction detection]{is an analysis that identifies statements that perform a reduction over a variable.}
 178
 179 \item[parallelism detection]{is a common name for analysis that detect if a loop can be run in parallel.}
 180
 181 \item[parallelism extraction]{is a common name for code transformations that modifies loop nest to make it legal to run them in parallel.}
 182
 183 \item[directive generation]{is a common name for code transformations that annotate the code with directives.}
 184
 185 \item[constant propagation]{is a pass that replaces a variable by its value when this value is known at compile time.}
 186
 187 \item[instruction selection]{is the process of mapping parts of the IR to machine instructions.}
 188
 189 \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.}
 190
 191 \item[statement isolation]{is the process of replacing all variables referenced in a statement by newly declared variables.
 192 A prologue and an epilogue are added to copy old variable values to new variable, back and forth.}
 193
 194 \item[array linearization]{is the process of converting multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.}
 195
 196 \item[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.}
 197
 198 \item[flatten code]{is the process of pruning a function body from declaration blocks so that all declarations are made at the top level.}
 199
 200 \item[strength reduction]{is the process of replacing an operation by an operation of lower cost.}
 201
 202 \item[split update operator]{is the process of replacing an update operator by its expanded form.}
 203
 204 \item[n address code generation]{is the process of splitting complex expression in simpler ones that take at most \(n\) operands.}
 205
 206 \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.}
 207
 208 \item[redundant load-store elimination]{is an inter procedural transformation that optimizes data transfers by delaying and merging them.}
 209
 210 \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.}
 211
 212 \item[loop rerolling]{finds manually unrolled loop and replace them by their non-unrolled version.}
 213
 214 \end{description}
 215
 216 \nocite{*}
 217 \bibliographystyle{alpha}
 218 \bibliography{\jobname}
 219
 220 \end{document}