1 \documentclass[pdftex, a4paper, 11pt]{report}
3 \usepackage[utf8]{inputenc}
4 \usepackage[T1]{fontenc}
5 \usepackage[english]{babel}
6 \usepackage{lmodern}
8 \usepackage{listings}
9 \usepackage{hyperref}
12 \title{PIPS~--- List of code transformations}
16 \begin{document}
19 \chapter{List of Pips transformations}
21 \section{Memory allocation alteration}
23 \begin{description}
25 \item[scalar renaming]{is the process of renaming scalar variables to
26 suppress false data dependencies.}
28 \item[privatization]{is the process of detecting variables that are
29 private to a loop body, i.e.\ written first, then read.}
31 \end{description}
34 \section{Loop transformations}
36 \begin{description}
38 \item[loop unrolling]{
39 is a loop transformation.
40 Unrolling a loop by a factor of $n$ consists in the substitution of a loop
41 body by itself, replicated $n$ times. A prelude and/or postlude are
42 added to preserve the number of iteration.}
44 \item[loop fusion]{
45 is a loop transformation that replaces two loops by a single loops whose
46 body is the concatenation of the bodies of the two initial loops.}
48 \item[loop tiling]{
49 is a loop nest transformation that changes the loop execution order
50 through a partitions of the iteration space into
51 chunks, so that the iteration is performed over each chunk and in the
52 chunks.}
54 \item[loop interchange]{is a loop transformation that permutes two
55 loops from a loop nest.}
57 \item[loop unswitching]{is a loop transformation that replaces a
58 loop containing a test independent from the loop execution by a test
59 containing the loop without the test in both true and false branch.}
61 \item[loop normalization]{is a loop transformation that changes
62 the loop initial increment value or the loop range to enforce certain values,
63 generally~1.}
65 \end{description}
67 \section{Inter-procedural transformations}
69 \section{Base blocs transformations}
76 \begin{description}
79 \item[inlining]{
80 is a function transformation. Inlining a function
81 \texttt{foo} in its caller \texttt{bar} consists in the substitution
82 of the calls to \texttt{foo} in \texttt{bar} by the function body
83 after replacement of the formal parameters by their effective
84 parameters.
85 }
87 \item[forward substitution]{
88 is the process of replacing a reference read in an
89 expression by the latest expression affected to it.}
95 \item[reduction detection]{
96 is an analysis that identifies statements that perform a reduction over a
97 variable.}
99 \item[parallelism detection]{
100 is a common name for analysis that detect if a loop can be run in parallel.}
102 \item[parallelism extraction]{
103 is a common name for code transformations that modifies loop nest to make it legal to
104 run them in parallel.}
106 \item[directive generation]{
107 is a common name for code transformations that annotate the code with directives.}
109 \item[constant propagation]{
110 is a pass that replaces a variable by its value when this value is
111 known at compile time.}
113 \item[instruction selection]{
114 is the process of mapping parts of the IR to machine instructions.}
116 \item[goto elimination]{
117 is the process of replacing \texttt{goto} instructions by a hierarchical control flow
118 graph.}
119 \item[outlining]{
120 is the process of extracting part of a function body into a new function
121 and replacing it in the initial function by a function call.}
123 \item[common subexpression elimination]{
124 is the process of replacing similar expressions by a variable that holds
125 the result of their evaluation.}
129 \item[statement isolation]{is the process of replacing all
130 variables referenced in a statement by newly declared variables. A
131 prologue
132 and an epilogue are added to copy old variable values to new variable, back
133 and forth.}
135 \item[dead code elimination]{is the process of pruning from a
136 function all the statements whose results are
137 never used.}
139 \item[array linearization]{is the process of converting
140 multidimensional array into unidimensional arrays, possibly with a
141 conversion from array to pointer.}
143 \item[loop normalization]{is a loop transformation that changes
144 the loop initial increment value or the loop range to enforce certain values, generally~1.}
146 \item[iteration clamping]{is a loop transformation that extends
147 the loop range but guards the loop body with the former range.}
149 \item[flatten code]{is the process of pruning a function body from
150 declaration blocks so that all declarations are made at the top level.}
152 \item[strength reduction]{is the process of replacing an operation
153 by an operation of lower cost.}
155 \item[split update operator]{is the process of replacing an update
156 operator by its expanded form.}
158 \item[n address code generation]{is the process of splitting
159 complex expression in simpler ones that take at most $n$ operands.}
161 \item[memory footprint reduction]{is the process of tiling a loop
162 to make sure the iteration over the tile has a memory footprint bounded by
163 a given value.}
165 \item[redundant load-store elimination]{is an inter procedural transformation
166 that optimizes data transfers by delaying and merging them.}
168 \item[invariant code motion]{is a loop transformation that moves outside
169 of the loop
170 the code from its body that is independent from the iteration.}
174 \item[loop rerolling]{finds manually unrolled loop and replace
175 them by their non-unrolled version.}
176 \end{description}
179 \section{References}
182 \end{document}