New branch for the register allocator created

["Vladimir N. Makarov" <vmakarov at redhat dot com>]

 After long work on YARA, I've decided to make some code which could
be available for gcc-4.4.  One goal of YARA project is to rid off
reload.  I found after starting work on YARA for ppc, sparc and
itanium that it is very ambitions goal which can not be achieved soon.

 YARA has a flexible infrastructure which permits to try different
register allocator algorithms and I tried a lot of them: different
coalescing, register pressure reduction, and coloring techniques
including

 o Chaitin-Briggs coloring
 o priority based coloring
 o coloring based on cyclic interval graphs (FAT heuristic)
 o Callahan-Koblenz register allocation
 o their different modifications
 o a top down regional register allocation

 Unfortunately Callahan-Koblenz algorithm is patented in 1996 and can
not be used for gcc.  But the top-down regional register allocation
works as well as Callahan-Koblentz algorithm but it is simpler.  I
found that the two algorithms works best in gcc environment.

 So I am creating a new branch IRA which major goal is to make the
new register allocator ready to include it into gcc-4.4.  Therefore my
goal is to make it working for all major gcc platforms.  It means also
that the new register allocator will use the current reload pass.  I
called it Integrated Register Allocator (IRA) because it makes
coalescing and live range splitting not as separate passes
(Callahan-Koblenz allocator also has no separate passes for coalescing
and live range splitting).  Coalescing is achieved by hard register
preferencing during coloring and live range splitting is a achieved
by the regional based coloring.  The regional allocation algorithm
uses top-down approach.  First it run Chaitin-Briggs coloring on whole
program, then on loops, on their subloops and etc.  It propagates
register preferences from one level to another one and generates
load/store, register shuffles on loop borders if it is necessary.  As
a byproduct the register allocator can use only Chaitin-Briggs
coloring.

 Everybody is welcomed to try the branch.  I'd appreciate also any
work to implement IRA for other targets.  Currently it is implemented
only for x86, x86_64, ppc, itanium, and sparc.

Vlad

Index: svn.html
===================================================================
RCS file: /cvs/gcc/wwwdocs/htdocs/svn.html,v
retrieving revision 1.41
diff -u -p -r1.41 svn.html
--- svn.html	23 Nov 2006 19:07:08 -0000	1.41
+++ svn.html	15 Dec 2006 02:48:49 -0000
@@ -352,6 +352,19 @@ list therefore provides only some repres
  be removed.  Patches should be marked with <code>[addrmodes]</code> in
  the subject line, and only need approval (from Paolo Bonzini) if they may
  change the compiler output.  The branch is maintained by Paolo Bonzini.</dd>
+
+  <dt>ira</dt>
+  <dd>This branch contains Integrated Register Allocator (IRA).  It is
+  based on work done on yara-branch.  YARA branch is more a research
+  branch because one its goal (removing reload) is too remote.  IRA
+  branch is focused to adopt some code to the gcc mainline hopefully
+  for gcc-4.4.  IRA which uses the reload is called integrated because
+  register coalescing and register live range splitting are done
+  on-the-fly during coloring.  The branch is maintained by Vladimir
+  Makarov &lt; <a
+  href="mailto:vmakarov@redhat.com";>vmakarov@redhat.com</a>&gt; and
+  will be merged with mainline from time to time.  Patches will be
+  marked with the tag <code>[ira]</code> in the subject line.</dd>
</dl>

<h4>Architecture-specific</h4>