9253d86853a9af4bcf201ecafdde9d22d6107302
[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 \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}