pipstransfo.tex

   1 \documentclass[pdftex, a4paper, 11pt]{report}
   2
   3 \usepackage[utf8]{inputenc}
   4 \usepackage[T1]{fontenc}
   5 \usepackage[english]{babel}
   6
   7 \usepackage{listings}
   8 \usepackage{hyperref}
   9
  10
  11 \title{PIPS - List of code transformations}
  12
  13
  14
  15 \begin{document}
  16
  17
  18 \chapter{List of Pips transformations}
  19
  20 \section{Memory allocation alteration}
  21
  22 \begin{description}
  23
  24 \item[scalar renaming]{is the process of renaming scalar variables to
  25     suppress false data dependencies.}
  26
  27 \item[privatization]{is the process of detecting variables that are
  28     private to a loop body, i.e.\ written first, then read.}
  29
  30 \end{description}
  31
  32
  33 \section{Loop transformations}
  34
  35 \begin{description}
  36
  37 \item[loop unrolling]{
  38   is a loop transformation.
  39   Unrolling a loop by a factor of $n$ consists in the substitution of a loop
  40   body by itself, replicated $n$ times. A prelude and/or postlude are
  41   added to preserve the number of iteration.}
  42
  43 \item[loop fusion]{
  44   is a loop transformation that replaces two loops by a single loops whose
  45   body is the concatenation of the bodies of the two initial loops.}
  46
  47 \item[loop tiling]{
  48   is a loop nest transformation that changes the loop execution order
  49   through a partitions of the iteration space into
  50   chunks, so that the iteration is performed over each chunk and in the
  51   chunks.}
  52
  53 \item[loop interchange]{is a loop transformation that permutes two
  54   loops from a loop nest.}
  55
  56 \item[loop unswitching]{is a loop transformation that replaces a
  57   loop containing a test independent from the loop execution by a test
  58   containing the loop without the test in both true and false branch.}
  59
  60 \item[loop normalization]{is a loop transformation that changes
  61   the loop initial increment value or the loop range to enforce certain values,
  62   generally 1.}
  63
  64 \end{description}
  65
  66 \section{Inter-procedural transformations}
  67
  68 \section{Base blocs transformations}
  69
  70 \section{Dead code removal}
  71
  72
  73
  74
  75 \begin{description}
  76
  77
  78 \item[inlining]{
  79   is a function transformation. Inlining a function
  80   \texttt{foo} in its caller \texttt{bar} consists in the substitution
  81   of the calls to \texttt{foo} in \texttt{bar} by the function body
  82   after replacement of the formal parameters by their effective
  83   parameters.
  84 }
  85
  86 \item[forward substitution]{
  87   is the process of replacing a reference read in an
  88   expression by the latest expression affected to it.}
  89
  90
  91
  92
  93
  94 \item[reduction detection]{
  95   is an analysis that identifies statements that perform a reduction over a
  96   variable.}
  97
  98 \item[parallelism detection]{
  99   is a common name for analysis that detect if a loop can be run in parallel.}
 100
 101 \item[parallelism extraction]{
 102   is a common name for code transformations that modifies loop nest to make it legal to
 103   run them in parallel.}
 104
 105 \item[directive generation]{
 106   is a common name for code transformations that annotate the code with directives.}
 107
 108 \item[constant propagation]{
 109   is a pass that replaces a variable by its value when this value is
 110   known at compile time.}
 111
 112 \item[instruction selection]{
 113   is the process of mapping parts of the IR to machine instructions.}
 114
 115 \item[goto elimination]{
 116   is the process of replacing \texttt{goto} instructions by a hierarchical control flow
 117   graph.}
 118 \item[outlining]{
 119   is the process of extracting part of a function body into a new function
 120   and replacing it in the initial function by a function call.}
 121
 122 \item[common subexpression elimination]{
 123   is the process of replacing similar expressions by a variable that holds
 124   the result of their evaluation.}
 125
 126
 127
 128 \item[statement isolation]{is the process of replacing all
 129   variables referenced in a statement by newly declared variables. A
 130   prologue
 131   and an epilogue are added to copy old variable values to new variable, back
 132   and forth.}
 133
 134 \item[dead code elimination]{is the process of pruning from a
 135   function all the statements whose results are
 136   never used.}
 137
 138 \item[array linearization]{is the process of converting
 139   multidimensional array into unidimensional arrays, possibly with a
 140   conversion from array to pointer.}
 141
 142
 143
 144
 145
 146 \item[iteration clamping]{is a loop transformation that extends
 147   the loop range but guards the loop body with the former range.}
 148
 149 \item[flatten code]{is the process of pruning a function body from
 150   declaration blocks so that all declarations are made at the top level.}
 151
 152 \item[strength reduction]{is the process of replacing an operation
 153   by an operation of lower cost.}
 154
 155 \item[split update operator]{is the process of replacing an update
 156   operator by its expanded form.}
 157
 158 \item[n address code generation]{is the process of splitting
 159   complex expression in simpler ones that take at most $n$ operands.}
 160
 161 \item[memory footprint reduction]{is the process of tiling a loop
 162   to make sure the iteration over the tile has a memory footprint bounded by
 163   a given value.}
 164
 165 \item[redundant load-store elimination]{is an inter procedural transformation
 166   that optimizes data transfers by delaying and merging them.}
 167
 168 \item[invariant code motion]{is a loop transformation that moves outside
 169   of the loop
 170   the code from its body that is independent from the iteration.}
 171
 172
 173
 174 \item[loop rerolling]{finds manually unrolled loop and replace
 175   them by their non-unrolled version.}
 176 \end{description}
 177
 178
 179 \section{References}
 180
 181
 182 \end{document}