e9cd235ca0c5c91a77a6a94a66713368f7c8277c
[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 \title{\PIPS~--- List of code transformations}
15
16 \begin{document}
17
18 \chapter{Summary}
19
20 \section{SGuelton}
21
22 \begin{itemize}
23
24 % memory allocation alteration
25 \item scalar renaming
26 % loop transformations
27 \item loop unrolling
28 \item loop fusion
29 \item loop tiling
30 \item loop rerolling
31 \item loop interchange
32 \item loop normalization
33 % inter procedural transformations
34 \item inlining
35 % basic bloc transformations
36 \item forward substitution
37 % dead code removal
38 \item constant propagation
39 \item dead code elimination
40
41 % ??
42 \item array linearization
43 \item common subexpression elimination
44 \item directive generation
45 \item flatten code
46 \item goto elimination
47 \item instruction selection
48 \item invariant code motion
49 \item iteration clamping
50 \item loop unswitching
51 \item memory footprint reduction
52 \item n adress code generation
53 \item outlining
54 \item parallelism detection
55 \item parallelism extraction
56 \item privatization
57 \item reduction detection
58 \item redundant load-store elimination
59 \item split update operator
60 \item statement isolation
61 \item strengh reduction
62
63 \end{itemize}
64
65 \section{Teraops}
66
67 \begin{itemize}
68
69 % memory allocation alteration
70 \item scalar renaming
71 \item scalar/array expansion
72 \item scalar/array privatization
73 \item scalarization % according to .pdf, not supported by Pips
74 \item variable copying % not supported by Pips
75 % loop transformations
76 \item index set splitting % not supported by Pips
77 \item loop peeling % not supported by Pips
78 \item loop unrolling
79 \item loop rerolling % not supported by Pips
80 \item full loop unrolling
81 \item idiom recognition
82 \item unswitching % not supported by Pips
83 \item loop fusion % not supported by Pips
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 % not supported by Pips
89 \item loop skewing
90 \item non-unimodular loop transformation
91 \item strip-mining (loop sectionning)
92 \item loop coalescing/loop collapsing % not supported by Pips
93 \item loop tiling
94 \item loop parallelization
95 \item loop vectorization % not supported by Pips
96 \item loop invariant code motion
97 \item software pipelining % not supported by Pips
98 \item locality increazing
99 % interprocedural transformations
100 \item loop embedding/loop jamming % not supported by Pips
101 \item procedure inlining % not supported by Pips
102 \item procedure cloning
103 % basic bloc transformations
104 \item node splitting
105 \item forward expression substitution
106 \item induction variable substitution % not supported by Pips
107 \item if-conversion
108 \item statement reordering % not supported by Pips
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
118 \end{itemize}
119
120 \chapter{List of \PIPS transformations}
121
122 \section{Memory allocation alteration}
123
124 \begin{description}
125
126 \item[scalar renaming]{is the process of renaming scalar variables to suppress false data dependencies.}
127
128 \item[privatization]{is the process of detecting variables that are private to a loop body, i.e.\ written first, then read.}
129
130 \end{description}
131
132
133 \section{Loop transformations}
134
135 \begin{description}
136
137 \item[loop unrolling]{is a loop transformation.
138 Unrolling a loop by a factor of \(n\) consists in the substitution of a loop body by itself, replicated \(n\) times.
139 A prelude and/or postlude are added to preserve the number of iteration.}
140
141 \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.}
142
143 \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.}
144
145 \item[loop interchange]{is a loop transformation that permutes two loops from a loop nest.}
146
147 \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.}
148
149 \item[loop normalization]{is a loop transformation that changes the loop initial increment value or the loop range to enforce certain values, generally~1.}
150
151 \end{description}
152
153 \section{Interprocedural transformations}
154
155 \section{Base blocs transformations}
156
157 \section{Dead code removal}
158
159 \begin{description}
160
161 \item[inlining]{is a function transformation.
162 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.}
163
164 \item[forward substitution]{is the process of replacing a reference read in an expression by the latest expression affected to it.}
165
166 \item[reduction detection]{is an analysis that identifies statements that perform a reduction over a variable.}
167
168 \item[parallelism detection]{is a common name for analysis that detect if a loop can be run in parallel.}
169
170 \item[parallelism extraction]{is a common name for code transformations that modifies loop nest to make it legal to run them in parallel.}
171
172 \item[directive generation]{is a common name for code transformations that annotate the code with directives.}
173
174 \item[constant propagation]{is a pass that replaces a variable by its value when this value is known at compile time.}
175
176 \item[instruction selection]{is the process of mapping parts of the IR to machine instructions.}
177
178 \item[goto elimination]{is the process of replacing \texttt{goto} instructions by a hierarchical control flow graph.}
179
180 \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.}
181
182 \item[common subexpression elimination]{is the process of replacing similar expressions by a variable that holds the result of their evaluation.}
183
184 \item[statement isolation]{is the process of replacing all variables referenced in a statement by newly declared variables.
185 A prologue and an epilogue are added to copy old variable values to new variable, back and forth.}
186
187 \item[dead code elimination]{is the process of pruning from a function all the statements whose results are never used.}
188
189 \item[array linearization]{is the process of converting multidimensional array into unidimensional arrays, possibly with a conversion from array to pointer.}
190
191 \item[iteration clamping]{is a loop transformation that extends the loop range but guards the loop body with the former range.}
192
193 \item[flatten code]{is the process of pruning a function body from declaration blocks so that all declarations are made at the top level.}
194
195 \item[strength reduction]{is the process of replacing an operation by an operation of lower cost.}
196
197 \item[split update operator]{is the process of replacing an update operator by its expanded form.}
198
199 \item[n address code generation]{is the process of splitting complex expression in simpler ones that take at most \(n\) operands.}
200
201 \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.}
202
203 \item[redundant load-store elimination]{is an inter procedural transformation that optimizes data transfers by delaying and merging them.}
204
205 \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.}
206
207 \item[loop rerolling]{finds manually unrolled loop and replace them by their non-unrolled version.}
208
209 \end{description}
210
211 \nocite{*}
212 \bibliographystyle{alpha}
213 \bibliography{\jobname}
214
215 \end{document}