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