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