[tree-ssa, lno, web] Web page for the loop nest optimizer branch
Pop Sébastian
pop@gauvain.u-strasbg.fr
Sat Dec 27 16:12:00 GMT 2003
Hi,
The following patch updates the TODO list of the tree-ssa project,
and includes the first version of the lno-branch web page.
Both pages pass the w3 validator. Ok to commit?
Sebastian
Index: index.html
===================================================================
RCS file: /cvs/gcc/wwwdocs/htdocs/projects/tree-ssa/index.html,v
retrieving revision 1.26
diff -d -u -p -r1.26 index.html
--- index.html 5 Dec 2003 14:45:00 -0000 1.26
+++ index.html 27 Dec 2003 15:20:11 -0000
@@ -18,7 +18,7 @@
<li><a href="#unparse">Unparsing GENERIC trees</a></li>
<li><a href="#tb">Tree Browser</a></li>
<li><a href="#status">Implementation Status (last updated: 2003-11-22)</a></li>
-<li><a href="#todo">TODO list (last updated: 2003-11-22)</a></li>
+<li><a href="#todo">TODO list (last updated: 2003-12-27)</a></li>
</ul>
<hr />
@@ -376,21 +376,10 @@ welcome.</dd>
<dd>The existing implementation treats arrays as an opaque object. A
definition to an array location is treated as a definition for the
whole array.</dd>
-<dt><em>Search of loop induction variables</em></dt>
-<dd>This could be implemented using Michael Wolfe's algorithm <a
- href="http://citeseer.nj.nec.com/gerlek95beyond.html">Beyond Induction
- Variables</a>. This algorithm is implemented in the <a
- href="ftp://ftp.cse.ogi.edu/pub/mwolfe/nascent.tar.gz">Nascent
- Compiler</a>.</dd>
<dt><em>Pointer analysis (aliasing)</em></dt>
<dd>Dan Berlin is working on Andersen Points-to analysis.
Unfortunately we cannot implement Steengaard analysis due to
patent issues.</dd>
-<dt><em>Dependence graph</em></dt>
-<dd>This pass is almost implemented in <code>dependence.c</code> but it's not
- used. We can adapt this work by keeping the dependence tester, but get
- the information about array subscripts and loops from the GIMPLE
- representation.</dd>
</dl>
<h4>Basic scalar transformations</h4>
@@ -410,39 +399,12 @@ welcome.</dd>
http://www.pattosoft.com.au/jason/Papers/ValueRangeProp/</a>.</dd>
</dl>
-
<h4>Control transformations</h4>
<dl>
-<dt><em>Normalization of array access functions</em></dt>
-<dd>This pass should gather the information decomposed by
- gimplification into well formed access functions. A further
- simplification should simplify these functions in order to get
- functions of loop indices. This form is needed in dependence
- tests. The implementation of this normalization is very similar
- to the search of loop induction variables by following use-defs
- chains and reconstructing the corresponding tree. Arithmetic
- simplification of expressions can be performed since we work on
- integers.</dd>
-<dt><em>Loop canonicalization</em></dt>
-<dd>This pass should construct Fortran like loops: a single induction
- variable by loop, the iteration begins at zero, and a step of one.
- If a loop has more than one induction variables, then it is
- possible to choose one of them, and express other variables in
- function of the first one.</dd>
-<dt><em>Temporal locality of data references</em></dt>
-<dd>This pass builds a geometrical representation of the order in
- which data sets are accessed. It transforms loop iterations in
- order to keep data references in caches. The algorithm is
- described in these
- <a href="http://icps.u-strasbg.fr/pco/locality.htm">papers</a> and
- implemented in a source-to-source
- <a href="http://icps.u-strasbg.fr/cgi-bin/temporal/temporal.cgi">
- translator</a>
- for Fortran.</dd>
-<dt><em><a href="vectorization.html">Vectorization</a></em></dt>
-<dd>This pass should vectorize certain loops, using classic data dependence
- based approach.</dd>
+<dt><em>Loop nest optimizations</em></dt>
+<dd>The <a href="lno.html">lno-branch</a> contains preliminary patches
+ that aim at implementing tree level loop optimizations.</dd>
</dl>
Index: lno.html
===================================================================
RCS file: lno.html
diff -N lno.html
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lno.html 27 Dec 2003 15:20:11 -0000
@@ -0,0 +1,55 @@
+<html>
+<head>
+<title>Loop Nest Optimizer</title>
+</head>
+
+<body>
+<h1>Loop Nest Optimizer</h1>
+
+<p>This project aims at implementing a loop nest optimizer at the tree
+level. The <code>lno-branch</code> is based on the
+<a href="index.html">tree-ssa-20020619-branch</a>.</p>
+
+<h4>Passes in the branch</h4>
+<dl>
+<dt><em>The analysis of scalars evolutions</em></dt>
+<dd>This pass analyzes the evolution function of scalar variables.
+ It is based on the SSA and the loop hierarchy representations
+ of the program. The aim of the pass is to compute when possible
+ an approximation of the number of iterations of the natural loops.
+ A first <a href="http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf">
+ design document</a> describes the SSA based algorithm that has
+ been implemented.</dd>
+<dt><em>The analysis of data dependences</em></dt>
+<dd>The scalar evolution analyzer computes the data access functions.
+ Based on the evolution functions of two conflicting array accesses,
+ the data dependence testers try to determine the elements that
+ access the same memory location: the conflicting elements. The
+ classic distance and direction vectors are abstracted from the
+ representation of the conflicting elements.</dd>
+</dl>
+
+<h4>Next passes</h4>
+<dl>
+<dt><em><a href="vectorization.html">Vectorization</a></em></dt>
+<dd>This pass should vectorize certain loops, using classic data dependence
+ based approach.</dd>
+<dt><em>Elimination of redundant checks</em></dt>
+<dd>Based on the scalar evolutions informations, it is sometimes possible
+ to extend the range of action of the constant copy propagation after the
+ loop structures. Given an iteration domain, it is possible to detect
+ redundant checks that are sometimes introduced automatically by the compiler
+ (as in -fbounds-check).</dd>
+<dt><em>Temporal and spatial locality of data references</em></dt>
+<dd>This pass builds a geometrical representation of the order in
+ which data sets are accessed. It transforms the loop iterations
+ in order to keep the data references in caches. The algorithm is
+ described in these
+ <a href="http://icps.u-strasbg.fr/pco/locality.htm">papers</a>.
+ A more general framework for loop nests transformations has been
+ proposed using the same high level polyhedral representation:
+ <a href="http://www.lri.fr/~girbal/site_wrapit/">WRaP-IT</a>.</dd>
+</dl>
+
+</body>
+</html>
More information about the Gcc-patches
mailing list