added references
[pipstransfo.git] / 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 \nocite{*}
263 \bibliographystyle{alpha}
264 \bibliography{refs}
265
266
267 \end{document}