This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

PING: [wwwdocs] update project page of cfo-branch


Hi,

  This patch hasn't been reviewed yet.
  http://gcc.gnu.org/ml/gcc-patches/2005-01/msg01716.html

Could someone look into it?

Thanks,
  Gabor Loki

------------------------------------------------------------------------

Index: cfo.html
===================================================================
RCS file: /cvs/gcc/wwwdocs/htdocs/projects/cfo.html,v
retrieving revision 1.2
diff -u -r1.2 cfo.html
--- cfo.html 14 Jan 2005 12:41:50 -0000 1.2
+++ cfo.html 24 Jan 2005 14:55:42 -0000
@@ -9,14 +9,21 @@
<h2>Table of Contents</h2>
<ul>
-<li><a href="#news">Latest news (last updated: 2004-11-16)</a></li>
+<li><a href="#news">Latest news (last updated: 2005-01-24)</a></li>
<li><a href="#intro">Introduction</a></li>
<li><a href="#documentation">Documentation</a></li>
+<li><a href="#features">Features</a></li>
+<li><a href="#preresults">Preliminary results</a></li>
+<li><a href="#todo">To do</a></li>
</ul>
<h2><a name="news">Latest News</a></h2>
<dl>
+<dt>2005-01-24</dt>
+<dd><p>Some more details about the algorithms and some preliminary results +added. To-do list published.
+</p></dd>
<dt>2004-11-16</dt>
<dd><p>The branch is now open. Checkout the cfo-branch branch by following the
instructions found in the <a href="../../cvs.html">CVS documentation</a>.
@@ -25,6 +32,10 @@
<h2><a name="intro">Introduction</a></h2>
+<p>Code factoring is the name of a class of useful optimization techniques +developed especially for code size reduction. These approaches aim to reduce
+size by restructuring the code.</p>
+
<p>The goal of this project is to add a new extension for improving the code
size optimization of GCC with code factoring methods (code motion and merging
algorithms). The implementation currently resides on the branch.</p>
@@ -33,10 +44,86 @@
<p>The project includes the following two code factoring algorithms:</p>
<ul>
-<li>Local code factoring: This is a code motion technique. It tries to merge two
-identical instructions.</li>
-<li>Sequence abstraction: This algorithm merges identical code sequences. It is
-nearly the opposite of function inlining.</li>
+<li>Local code factoring: This is a code motion technique. The optimization +strategy of local factoring is to move identical instructions from basic blocks
+to their common predecessor or successor, if they have any. The semantics of +the program have to be preserved of course, therefore only those instructions +may be moved, which neither invalidate any existing dependences nor introduce +new ones. To obtain the best size reduction some of the instructions are moved +upward (code hoisting) to the common predecessor, while some are moved downward +(code sinking) to the common successor.<br />
+C code example:<br />
+<pre>
+// Original source // After local factoring
+{ {
+ I1; // <= HOIST
+ if ( cond ) if ( cond )
+ { {
+ I0; I0;
+ I1; // <= HOIST
+ I2; // <= SINK
+ I3; // <= SINK
+ } }
+ else else
+ { {
+ I1; // <= HOIST
+ I4; I4;
+ I5; I5;
+ I2; // <= SINK
+ I3; // <= SINK
+ } }
+ I2; // <= SINK
+ I3; // <= SINK
+} }
+</pre>
+</li>
+<li>Sequence abstraction: It is a size optimization method, which, unlike local +factoring, works with whole basic blocks instead of single instructions. The +main idea of this technique is to find identical sequences of code, which can be +turned into procedures and then replace all occurences with calls to the newly +created subrutine. It is kind of an opposite of function inlining.<br />
+C code example:<br />
+<pre>
+// Original source // After sequence abstraction
+{ {
+ void *jump_label;
+ ... ...
+ jump_label = &amp;&amp;exit_0;
+ entry_0:
+ I0; I0;
+ I1; I1;
+ I2; I2;
+ I3; I3;
+ goto *jump_label;
+ exit_0:
+ ... ...
+ jump_label = &amp;&amp;exit_1;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_1:
+ ... ...
+ jump_label = &amp;&amp;exit_2;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_2:
+ ... ...
+ jump_label = &amp;&amp;exit_3;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_3:
+ ... ...
+} }
+</pre>
+</li>
</ul>
<p>Both algorithms have an opportunity of working on two different levels @@ -47,5 +134,77 @@
<a href="http://www.gccsummit.org/2004/2004-GCC-Summit-Proceedings.pdf";>
GCC Summit Proceedings (2004)</a>.</p>
+<h2><a name="features">Features</a></h2>
+
+<p>Currently the following algorithms are implemented in the branch:</p>
+
+<ul>
+<li>Local factoring on RTL (-frtl-lfact)</li>
+<li>Hoisting part of the local factoring on Tree-SSA (-ftree-lfact)</li>
+<li>Sequence abstraction on RTL (-fsequence-abstraction)</li>
+</ul>
+
+<h2><a name="preresults">Preliminary results</a></h2>
+
+<p>The following results have been prepared using the +<a href="http://www.csibe.org";>CSiBE</a> benchmark with respect to the mainline
+at the last merge (2004-11-16).</p>
+
+<table width="50%" border="1">
+<tr>
+ <td>&nbsp;</td>
+ <td align="center" colspan="2"><b>Code size save</b></td>
+ <td align="center" colspan="2"><b>Compilation time multiplier</b></td>
+</tr>
+<tr>
+ <td>Target</td>
+ <td align="center">arm-elf</td>
+ <td align="center">i386-elf</td>
+ <td align="center">arm-elf</td>
+ <td align="center">i386-elf</td>
+</tr>
+<tr>
+ <td>Sequence abstraction on RTL</td>
+ <td align="right">2.1%</td>
+ <td align="right">1.5%</td>
+
+ <td align="right">2.3</td>
+ <td align="right">1.4</td>
+</tr>
+<tr>
+ <td>Local factoring on RTL</td>
+ <td align="right">0.1%</td>
+ <td align="right">0.03%</td>
+
+ <td align="right">1.01</td>
+ <td align="right">1.01</td>
+</tr>
+<tr>
+ <td>Local factoring on Tree-SSA</td>
+ <td align="right">0.1%</td>
+ <td align="right">0.02%</td>
+
+ <td align="right">1.04</td>
+ <td align="right">1.03</td>
+</tr>
+<tr>
+ <td><b>Overall</b></td>
+ <td align="right"><b>2.4%</b></td>
+ <td align="right"><b>1.5%</b></td>
+
+ <td align="right"><b>2.4</b></td>
+ <td align="right"><b>1.5</b></td>
+</tr>
+</table>
+
+<h2><a name="todo">To do</a></h2>
+
+<ul>
+<li>Implement sinking part of local factoring on Tree-SSA</li>
+<li>Implement sequence abstraction on Tree-SSA</li>
+<li>Improve the compilation time of the sequence abstraction using
+fingerprinting</li>
+</ul>
+
</body>
</html>




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]