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