[tree-ssa, lno, web] Web page for the loop nest optimizer branch

[Pop Sébastian <pop at gauvain dot u-strasbg dot fr>]

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>