2002-07-15 Michael Matz <matz@suse.de>,

            Daniel Berlin  <dberlin@dberlin.org>,
	    Denis Chertykov  <denisc@overta.ru>

	Add a new register allocator.

	* ra.c: New file.
	* ra.h: New file.
	* ra-build.c: New file.
	* ra-colorize.c: New file.
	* ra-debug.c: New file.
	* ra-rewrite.c: New file.

	* Makefile.in (ra.o, ra-build.o, ra-colorize.o, ra-debug.o,
	(ra-rewrite.o): New .o files for libbackend.a.
	(GTFILES): Add basic-block.h.

	* toplev.c (flag_new_regalloc): New.
	(f_options): New option "new-ra".
	(rest_of_compilation): Call initialize_uninitialized_subregs()
	only for the old allocator.  If flag_new_regalloc is set, call
	new allocator, instead of local_alloc(), global_alloc() and
	friends.

	* doc/invoke.texi: Document -fnew-ra.
	* basic-block.h (FOR_ALL_BB): New.
	* config/rs6000/rs6000.c (print_operand): Write small constants
	as @l+80.

	* df.c (read_modify_subreg_p): Narrow down cases for a rmw subreg.
	(df_reg_table_realloc): Make size at least as large as max_reg_num().
	(df_insn_table_realloc): Size argument now is absolute, not relative.
	Changed all callers.

	* gengtype.c (main): Add the pseudo-type "HARD_REG_SET".
	* regclass.c (reg_scan_mark_refs): Ignore NULL rtx's.

	2002-06-20  Michael Matz  <matz@suse.de>

	* df.h (struct ref.id): Make unsigned.
	* df.c (df_bb_reg_def_chain_create): Remove unsigned cast.

	2002-06-13  Michael Matz  <matz@suse.de>

	* df.h (DF_REF_MODE_CHANGE): New flag.
	* df.c (df_def_record_1, df_uses_record): Set this flag for refs
	involving subregs with invalid mode changes, when
	CLASS_CANNOT_CHANGE_MODE is defined.

	2002-05-07  Michael Matz  <matz@suse.de>

	* reload1.c (fixup_abnormal_edges): Don't insert on NULL edge.

	2002-05-03  Michael Matz  <matz@suse.de>

	* sbitmap.c (sbitmap_difference): Accept sbitmaps of different size.

	Sat Feb  2 18:58:07 2002  Denis Chertykov  <denisc@overta.ru>

	* regclass.c (regclass): Work with all regs which have sets or
	refs.
	(reg_scan_mark_refs): Count regs inside (clobber ...).

	2002-01-04  Michael Matz  <matzmich@cs.tu-berlin.de>

	* df.c (df_ref_record): Correctly calculate SUBREGs of hardregs.
	(df_bb_reg_def_chain_create, df_bb_reg_use_chain_create): Only
	add new refs.
	(df_bb_refs_update): Don't clear insns_modified here, ...
	(df_analyse): ... but here.

	* sbitmap.c (dump_sbitmap_file): New.
	(debug_sbitmap): Use it.

	* sbitmap.h (dump_sbitmap_file): Add prototype.

	2001-08-07  Daniel Berlin  <dan@cgsoftware.com>

	* df.c (df_insn_modify): Grow the UID table if necessary, rather
	than assume all emits go through df_insns_modify.

	2001-07-26  Daniel Berlin  <dan@cgsoftware.com>

	* regclass.c (reg_scan_mark_refs): When we increase REG_N_SETS,
	increase REG_N_REFS (like flow does), so that regclass doesn't
	think a reg is useless, and thus, not calculate a class, when it
	really should have.

	2001-01-28  Daniel Berlin  <dberlin@redhat.com>

	* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP_REV): New macro, needed for
	dataflow analysis.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@55458 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 3264 insertions, 0 deletions

diff --git a/gcc/ra-build.c b/gcc/ra-build.c
new file mode 100644
index 00000000000..d3e24bc8cb9
--- /dev/null
+++ b/gcc/ra-build.c
@@ -0,0 +1,3264 @@
+/* Graph coloring register allocator
+   Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+   Contributed by Michael Matz <matz@suse.de>
+   and Daniel Berlin <dan@cgsoftware.com>
+
+   This file is part of GCC.
+
+   GCC is free software; you can redistribute it and/or modify it under the
+   terms of the GNU General Public License as published by the Free Software
+   Foundation; either version 2, or (at your option) any later version.
+
+   GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+   details.
+
+   You should have received a copy of the GNU General Public License along
+   with GCC; see the file COPYING.  If not, write to the Free Software
+   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "function.h"
+#include "regs.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "df.h"
+#include "output.h"
+#include "ggc.h"
+#include "ra.h"
+
+/* This file is part of the graph coloring register alloctor.
+   It deals with building the interference graph.  When rebuilding
+   the graph for a function after spilling, we rebuild only those
+   parts needed, i.e. it works incrementally.
+
+   The first part (the functions called from build_web_parts_and_conflicts()
+   ) constructs a web_part for each pseudo register reference in the insn
+   stream, then goes backward from each use, until it reaches defs for that
+   pseudo.  While going back it remember seen defs for other registers as
+   conflicts.  By connecting the uses and defs, which reach each other, webs
+   (or live ranges) are built conceptually.
+
+   The second part (make_webs() and childs) deals with converting that
+   structure to the nodes and edges, on which our interference graph is
+   built.  For each root web part constructed above, an instance of struct
+   web is created.  For all subregs of pseudos, which matter for allocation,
+   a subweb of the corresponding super web is built.  Finally all the
+   conflicts noted in the first part (as bitmaps) are transformed into real
+   edges.
+
+   As part of that process the webs are also classified (their spill cost
+   is calculated, and if they are spillable at all, and if not, for what
+   reason; or if they are rematerializable), and move insns are collected,
+   which are potentially coalescable.
+
+   The top-level entry of this file (build_i_graph) puts it all together,
+   and leaves us with a complete interference graph, which just has to
+   be colored.  */
+
+
+struct curr_use;
+
+static unsigned HOST_WIDE_INT rtx_to_undefined PARAMS ((rtx));
+static bitmap find_sub_conflicts PARAMS ((struct web_part *, unsigned int));
+static bitmap get_sub_conflicts PARAMS ((struct web_part *, unsigned int));
+static unsigned int undef_to_size_word PARAMS ((rtx, unsigned HOST_WIDE_INT *));
+static bitmap undef_to_bitmap PARAMS ((struct web_part *,
+				       unsigned HOST_WIDE_INT *));
+static struct web_part * find_web_part_1 PARAMS ((struct web_part *));
+static struct web_part * union_web_part_roots
+				PARAMS ((struct web_part *, struct web_part *));
+static int defuse_overlap_p_1 PARAMS ((rtx, struct curr_use *));
+static int live_out_1 PARAMS ((struct df *, struct curr_use *, rtx));
+static int live_out PARAMS ((struct df *, struct curr_use *, rtx));
+static rtx live_in_edge PARAMS (( struct df *, struct curr_use *, edge));
+static void live_in PARAMS ((struct df *, struct curr_use *, rtx));
+static int copy_insn_p PARAMS ((rtx, rtx *, rtx *));
+static void remember_move PARAMS ((rtx));
+static void handle_asm_insn PARAMS ((struct df *, rtx));
+static void prune_hardregs_for_mode PARAMS ((HARD_REG_SET *,
+					     enum machine_mode));
+static void init_one_web_common PARAMS ((struct web *, rtx));
+static void init_one_web PARAMS ((struct web *, rtx));
+static void reinit_one_web PARAMS ((struct web *, rtx));
+static struct web * add_subweb PARAMS ((struct web *, rtx));
+static struct web * add_subweb_2 PARAMS ((struct web *, unsigned int));
+static void init_web_parts PARAMS ((struct df *));
+static void copy_conflict_list PARAMS ((struct web *));
+static void add_conflict_edge PARAMS ((struct web *, struct web *));
+static void build_inverse_webs PARAMS ((struct web *));
+static void copy_web PARAMS ((struct web *, struct web_link **));
+static void compare_and_free_webs PARAMS ((struct web_link **));
+static void init_webs_defs_uses PARAMS ((void));
+static unsigned int parts_to_webs_1 PARAMS ((struct df *, struct web_link **,
+					     struct df_link *));
+static void parts_to_webs PARAMS ((struct df *));
+static void reset_conflicts PARAMS ((void));
+static void check_conflict_numbers PARAMS ((void));
+static void conflicts_between_webs PARAMS ((struct df *));
+static void remember_web_was_spilled PARAMS ((struct web *));
+static void detect_spill_temps PARAMS ((void));
+static int contains_pseudo PARAMS ((rtx));
+static int want_to_remat PARAMS ((rtx x));
+static void detect_remat_webs PARAMS ((void));
+static void determine_web_costs PARAMS ((void));
+static void detect_webs_set_in_cond_jump PARAMS ((void));
+static void make_webs PARAMS ((struct df *));
+static void moves_to_webs PARAMS ((struct df *));
+static void connect_rmw_web_parts PARAMS ((struct df *));
+static void update_regnos_mentioned PARAMS ((void));
+static void livethrough_conflicts_bb PARAMS ((basic_block));
+static void init_bb_info PARAMS ((void));
+static void free_bb_info PARAMS ((void));
+static void build_web_parts_and_conflicts PARAMS ((struct df *));
+
+
+/* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
+   edge.  */
+static sbitmap live_over_abnormal;
+
+/* To cache if we already saw a certain edge while analyzing one
+   use, we use a tick count incremented per use.  */
+static unsigned int visited_pass;
+
+/* A sbitmap of UIDs of move insns, which we already analyzed.  */
+static sbitmap move_handled;
+
+/* One such structed is allocated per insn, and traces for the currently
+   analyzed use, which web part belongs to it, and how many bytes of
+   it were still undefined when that insn was reached.  */
+struct visit_trace
+{
+  struct web_part *wp;
+  unsigned HOST_WIDE_INT undefined;
+};
+/* Indexed by UID.  */
+static struct visit_trace *visit_trace;
+
+/* Per basic block we have one such structure, used to speed up
+   the backtracing of uses.  */
+struct ra_bb_info
+{
+  /* The value of visited_pass, as the first insn of this BB was reached
+     the last time.  If this equals the current visited_pass, then
+     undefined is valid.  Otherwise not.  */
+  unsigned int pass;
+  /* The still undefined bytes at that time.  The use to which this is
+     relative is the current use.  */
+  unsigned HOST_WIDE_INT undefined;
+  /* Bit regno is set, if that regno is mentioned in this BB as a def, or
+     the source of a copy insn.  In these cases we can not skip the whole
+     block if we reach it from the end.  */
+  bitmap regnos_mentioned;
+  /* If a use reaches the end of a BB, and that BB doesn't mention its
+     regno, we skip the block, and remember the ID of that use
+     as living throughout the whole block.  */
+  bitmap live_throughout;
+  /* The content of the aux field before placing a pointer to this
+     structure there.  */
+  void *old_aux;
+};
+
+/* We need a fast way to describe a certain part of a register.
+   Therefore we put together the size and offset (in bytes) in one
+   integer.  */
+#define BL_TO_WORD(b, l) ((((b) & 0xFFFF) << 16) | ((l) & 0xFFFF))
+#define BYTE_BEGIN(i) (((unsigned int)(i) >> 16) & 0xFFFF)
+#define BYTE_LENGTH(i) ((unsigned int)(i) & 0xFFFF)
+
+/* For a REG or SUBREG expression X return the size/offset pair
+   as an integer.  */
+
+unsigned int
+rtx_to_bits (x)
+     rtx x;
+{
+  unsigned int len, beg;
+  len = GET_MODE_SIZE (GET_MODE (x));
+  beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0;
+  return BL_TO_WORD (beg, len);
+}
+
+/* X is a REG or SUBREG rtx.  Return the bytes it touches as a bitmask.  */
+
+static unsigned HOST_WIDE_INT
+rtx_to_undefined (x)
+     rtx x;
+{
+  unsigned int len, beg;
+  unsigned HOST_WIDE_INT ret;
+  len = GET_MODE_SIZE (GET_MODE (x));
+  beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0;
+  ret = ~ ((unsigned HOST_WIDE_INT) 0);
+  ret = (~(ret << len)) << beg;
+  return ret;
+}
+
+/* We remember if we've analyzed an insn for being a move insn, and if yes
+   between which operands.  */
+struct copy_p_cache
+{
+  int seen;
+  rtx source;
+  rtx target;
+};
+
+/* On demand cache, for if insns are copy insns, and if yes, what
+   source/target they have.  */
+static struct copy_p_cache * copy_cache;
+
+int *number_seen;
+
+/* For INSN, return nonzero, if it's a move insn, we consider to coalesce
+   later, and place the operands in *SOURCE and *TARGET, if they are
+   not NULL.  */
+
+static int
+copy_insn_p (insn, source, target)
+     rtx insn;
+     rtx *source;
+     rtx *target;
+{
+  rtx d, s;
+  unsigned int d_regno, s_regno;
+  int uid = INSN_UID (insn);
+
+  if (!INSN_P (insn))
+    abort ();
+
+  /* First look, if we already saw this insn.  */
+  if (copy_cache[uid].seen)
+    {
+      /* And if we saw it, if it's actually a copy insn.  */
+      if (copy_cache[uid].seen == 1)
+	{
+	  if (source)
+	    *source = copy_cache[uid].source;
+	  if (target)
+	    *target = copy_cache[uid].target;
+	  return 1;
+	}
+      return 0;
+    }
+
+  /* Mark it as seen, but not being a copy insn.  */
+  copy_cache[uid].seen = 2;
+  insn = single_set (insn);
+  if (!insn)
+    return 0;
+  d = SET_DEST (insn);
+  s = SET_SRC (insn);
+
+  /* We recognize moves between subreg's as copy insns.  This is used to avoid
+     conflicts of those subwebs.  But they are currently _not_ used for
+     coalescing (the check for this is in remember_move() below).  */
+  while (GET_CODE (d) == STRICT_LOW_PART)
+    d = XEXP (d, 0);
+  if (GET_CODE (d) != REG
+      && (GET_CODE (d) != SUBREG || GET_CODE (SUBREG_REG (d)) != REG))
+    return 0;
+  while (GET_CODE (s) == STRICT_LOW_PART)
+    s = XEXP (s, 0);
+  if (GET_CODE (s) != REG
+      && (GET_CODE (s) != SUBREG || GET_CODE (SUBREG_REG (s)) != REG))
+    return 0;
+
+  s_regno = (unsigned) REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s);
+  d_regno = (unsigned) REGNO (GET_CODE (d) == SUBREG ? SUBREG_REG (d) : d);
+
+  /* Copies between hardregs are useless for us, as not coalesable anyway. */
+  if ((s_regno < FIRST_PSEUDO_REGISTER
+       && d_regno < FIRST_PSEUDO_REGISTER)
+      || s_regno >= max_normal_pseudo
+      || d_regno >= max_normal_pseudo)
+    return 0;
+
+  if (source)
+    *source = s;
+  if (target)
+    *target = d;
+
+  /* Still mark it as seen, but as a copy insn this time.  */
+  copy_cache[uid].seen = 1;
+  copy_cache[uid].source = s;
+  copy_cache[uid].target = d;
+  return 1;
+}
+
+/* We build webs, as we process the conflicts.  For each use we go upward
+   the insn stream, noting any defs as potentially conflicting with the
+   current use.  We stop at defs of the current regno.  The conflicts are only
+   potentially, because we may never reach a def, so this is an undefined use,
+   which conflicts with nothing.  */
+
+
+/* Given a web part WP, and the location of a reg part SIZE_WORD
+   return the conflict bitmap for that reg part, or NULL if it doesn't
+   exist yet in WP.  */
+
+static bitmap
+find_sub_conflicts (wp, size_word)
+     struct web_part *wp;
+     unsigned int size_word;
+{
+  struct tagged_conflict *cl;
+  cl = wp->sub_conflicts;
+  for (; cl; cl = cl->next)
+    if (cl->size_word == size_word)
+      return cl->conflicts;
+  return NULL;
+}
+
+/* Similar to find_sub_conflicts(), but creates that bitmap, if it
+   doesn't exist.  I.e. this never returns NULL.  */
+
+static bitmap
+get_sub_conflicts (wp, size_word)
+     struct web_part *wp;
+     unsigned int size_word;
+{
+  bitmap b = find_sub_conflicts (wp, size_word);
+  if (!b)
+    {
+      struct tagged_conflict *cl =
+	(struct tagged_conflict *) ra_alloc (sizeof *cl);
+      cl->conflicts = BITMAP_XMALLOC ();
+      cl->size_word = size_word;
+      cl->next = wp->sub_conflicts;
+      wp->sub_conflicts = cl;
+      b = cl->conflicts;
+    }
+  return b;
+}
+
+/* Helper table for undef_to_size_word() below for small values
+   of UNDEFINED.  Offsets and lengths are byte based.  */
+static struct undef_table_s {
+  unsigned int new_undef;
+  /* size | (byte << 16)  */
+  unsigned int size_word;
+} undef_table [] = {
+  { 0, BL_TO_WORD (0, 0)}, /* 0 */
+  { 0, BL_TO_WORD (0, 1)},
+  { 0, BL_TO_WORD (1, 1)},
+  { 0, BL_TO_WORD (0, 2)},
+  { 0, BL_TO_WORD (2, 1)}, /* 4 */
+  { 1, BL_TO_WORD (2, 1)},
+  { 2, BL_TO_WORD (2, 1)},
+  { 3, BL_TO_WORD (2, 1)},
+  { 0, BL_TO_WORD (3, 1)}, /* 8 */
+  { 1, BL_TO_WORD (3, 1)},
+  { 2, BL_TO_WORD (3, 1)},
+  { 3, BL_TO_WORD (3, 1)},
+  { 0, BL_TO_WORD (2, 2)}, /* 12 */
+  { 1, BL_TO_WORD (2, 2)},
+  { 2, BL_TO_WORD (2, 2)},
+  { 0, BL_TO_WORD (0, 4)}};
+
+/* Interpret *UNDEFINED as bitmask where each bit corresponds to a byte.
+   A set bit means an undefined byte.  Factor all undefined bytes into
+   groups, and return a size/ofs pair of consecutive undefined bytes,
+   but according to certain borders.  Clear out those bits corrsponding
+   to bytes overlaid by that size/ofs pair.  REG is only used for
+   the mode, to detect if it's a floating mode or not.
+
+   For example:	*UNDEFINED	size+ofs	new *UNDEFINED
+		 1111		4+0		  0
+		 1100		2+2		  0
+		 1101		2+2		  1
+		 0001		1+0		  0
+		10101		1+4		101
+
+   */
+
+static unsigned int
+undef_to_size_word (reg, undefined)
+     rtx reg;
+     unsigned HOST_WIDE_INT *undefined;
+{
+  /* When only the lower four bits are possibly set, we use
+     a fast lookup table.  */
+  if (*undefined <= 15)
+    {
+      struct undef_table_s u;
+      u = undef_table[*undefined];
+      *undefined = u.new_undef;
+      return u.size_word;
+    }
+
+  /* Otherwise we handle certain cases directly.  */
+  switch (*undefined)
+    {
+      case 0x00f0 : *undefined = 0; return BL_TO_WORD (4, 4);
+      case 0x00ff : *undefined = 0; return BL_TO_WORD (0, 8);
+      case 0x0f00 : *undefined = 0; return BL_TO_WORD (8, 4);
+      case 0x0ff0 : *undefined = 0xf0; return BL_TO_WORD (8, 4);
+      case 0x0fff :
+	if (INTEGRAL_MODE_P (GET_MODE (reg)))
+	  { *undefined = 0xff; return BL_TO_WORD (8, 4); }
+	else
+	  { *undefined = 0; return BL_TO_WORD (0, 12); /* XFmode */ }
+      case 0xf000 : *undefined = 0; return BL_TO_WORD (12, 4);
+      case 0xff00 : *undefined = 0; return BL_TO_WORD (8, 8);
+      case 0xfff0 : *undefined = 0xf0; return BL_TO_WORD (8, 8);
+      case 0xffff : *undefined = 0; return BL_TO_WORD (0, 16);
+
+      /* And if nothing matched fall back to the general solution.
+	 For now unknown undefined bytes are converted to sequences
+	 of maximal length 4 bytes.  We could make this larger if
+	 necessary.  */
+      default :
+	{
+	  unsigned HOST_WIDE_INT u = *undefined;
+	  int word;
+	  struct undef_table_s tab;
+	  for (word = 0; (u & 15) == 0; word += 4)
+	    u >>= 4;
+	  u = u & 15;
+	  tab = undef_table[u];
+	  u = tab.new_undef;
+	  u = (*undefined & ~((unsigned HOST_WIDE_INT)15 << word))
+	      | (u << word);
+	  *undefined = u;
+	  /* Size remains the same, only the begin is moved up move bytes.  */
+	  return tab.size_word + BL_TO_WORD (word, 0);
+	}
+	break;
+    }
+}
+
+/* Put the above three functions together.  For a set of undefined bytes
+   as bitmap *UNDEFINED, look for (create if necessary) and return the
+   corresponding conflict bitmap.  Change *UNDEFINED to remove the bytes
+   covered by the part for that bitmap.  */
+
+static bitmap
+undef_to_bitmap (wp, undefined)
+     struct web_part *wp;
+     unsigned HOST_WIDE_INT *undefined;
+{
+  unsigned int size_word = undef_to_size_word (DF_REF_REAL_REG (wp->ref),
+					       undefined);
+  return get_sub_conflicts (wp, size_word);
+}
+
+/* Returns the root of the web part P is a member of.  Additionally
+   it compresses the path.  P may not be NULL.  */
+
+static struct web_part *
+find_web_part_1 (p)
+     struct web_part *p;
+{
+  struct web_part *r = p;
+  struct web_part *p_next;
+  while (r->uplink)
+    r = r->uplink;
+  for (; p != r; p = p_next)
+    {
+      p_next = p->uplink;
+      p->uplink = r;
+    }
+  return r;
+}
+
+/* Fast macro for the common case (WP either being the root itself, or
+   the end of an already compressed path.  */
+
+#define find_web_part(wp) ((! (wp)->uplink) ? (wp) \
+  : (! (wp)->uplink->uplink) ? (wp)->uplink : find_web_part_1 (wp))
+
+/* Unions together the parts R1 resp. R2 is a root of.
+   All dynamic information associated with the parts (number of spanned insns
+   and so on) is also merged.
+   The root of the resulting (possibly larger) web part is returned.  */
+
+static struct web_part *
+union_web_part_roots (r1, r2)
+     struct web_part *r1, *r2;
+{
+  if (r1 != r2)
+    {
+      /* The new root is the smaller (pointerwise) of both.  This is crucial
+         to make the construction of webs from web parts work (so, when
+	 scanning all parts, we see the roots before all it's childs).
+         Additionally this ensures, that if the web has a def at all, than
+         the root is a def (because all def parts are before use parts in the
+	 web_parts[] array), or put another way, as soon, as the root of a
+         web part is not a def, this is an uninitialized web part.  The
+         way we construct the I-graph ensures, that if a web is initialized,
+         then the first part we find (besides trivial 1 item parts) has a
+         def.  */
+      if (r1 > r2)
+	{
+	  struct web_part *h = r1;
+	  r1 = r2;
+	  r2 = h;
+	}
+      r2->uplink = r1;
+      num_webs--;
+
+      /* Now we merge the dynamic information of R1 and R2.  */
+      r1->spanned_deaths += r2->spanned_deaths;
+
+      if (!r1->sub_conflicts)
+	r1->sub_conflicts = r2->sub_conflicts;
+      else if (r2->sub_conflicts)
+	/* We need to merge the conflict bitmaps from R2 into R1.  */
+	{
+	  struct tagged_conflict *cl1, *cl2;
+	  /* First those from R2, which are also contained in R1.
+	     We union the bitmaps, and free those from R2, resetting them
+	     to 0.  */
+	  for (cl1 = r1->sub_conflicts; cl1; cl1 = cl1->next)
+	    for (cl2 = r2->sub_conflicts; cl2; cl2 = cl2->next)
+	      if (cl1->size_word == cl2->size_word)
+		{
+		  bitmap_operation (cl1->conflicts, cl1->conflicts,
+				    cl2->conflicts, BITMAP_IOR);
+		  BITMAP_XFREE (cl2->conflicts);
+		  cl2->conflicts = NULL;
+		}
+	  /* Now the conflict lists from R2 which weren't in R1.
+	     We simply copy the entries from R2 into R1' list.  */
+	  for (cl2 = r2->sub_conflicts; cl2;)
+	    {
+	      struct tagged_conflict *cl_next = cl2->next;
+	      if (cl2->conflicts)
+		{
+		  cl2->next = r1->sub_conflicts;
+		  r1->sub_conflicts = cl2;
+		}
+	      cl2 = cl_next;
+	    }
+	}
+      r2->sub_conflicts = NULL;
+      r1->crosses_call |= r2->crosses_call;
+    }
+  return r1;
+}
+
+/* Convenience macro, that is cabable of unioning also non-roots.  */
+#define union_web_parts(p1, p2) \
+  ((p1 == p2) ? find_web_part (p1) \
+      : union_web_part_roots (find_web_part (p1), find_web_part (p2)))
+
+/* Remember that we've handled a given move, so we don't reprocess it.  */
+
+static void
+remember_move (insn)
+     rtx insn;
+{
+  if (!TEST_BIT (move_handled, INSN_UID (insn)))
+    {
+      rtx s, d;
+      SET_BIT (move_handled, INSN_UID (insn));
+      if (copy_insn_p (insn, &s, &d))
+	{
+	  /* Some sanity test for the copy insn. */
+	  struct df_link *slink = DF_INSN_USES (df, insn);
+	  struct df_link *link = DF_INSN_DEFS (df, insn);
+	  if (!link || !link->ref || !slink || !slink->ref)
+	    abort ();
+	  /* The following (link->next != 0) happens when a hardreg
+	     is used in wider mode (REG:DI %eax).  Then df.* creates
+	     a def/use for each hardreg contained therein.  We only
+	     allow hardregs here.  */
+	  if (link->next
+	      && DF_REF_REGNO (link->next->ref) >= FIRST_PSEUDO_REGISTER)
+	    abort ();
+	}
+      else
+	abort ();
+      /* XXX for now we don't remember move insns involving any subregs.
+	 Those would be difficult to coalesce (we would need to implement
+	 handling of all the subwebs in the allocator, including that such
+	 subwebs could be source and target of coalesing).  */
+      if (GET_CODE (s) == REG && GET_CODE (d) == REG)
+	{
+	  struct move *m = (struct move *) ra_calloc (sizeof (struct move));
+	  struct move_list *ml;
+	  m->insn = insn;
+	  ml = (struct move_list *) ra_alloc (sizeof (struct move_list));
+	  ml->move = m;
+	  ml->next = wl_moves;
+	  wl_moves = ml;
+	}
+    }
+}
+
+/* This describes the USE currently looked at in the main-loop in
+   build_web_parts_and_conflicts().  */
+struct curr_use {
+  struct web_part *wp;
+  /* This has a 1-bit for each byte in the USE, which is still undefined.  */
+  unsigned HOST_WIDE_INT undefined;
+  /* For easy access.  */
+  unsigned int regno;
+  rtx x;
+  /* If some bits of this USE are live over an abnormal edge.  */
+  unsigned int live_over_abnormal;
+};
+
+/* Returns nonzero iff rtx DEF and USE have bits in common (but see below).
+   It is only called with DEF and USE being (reg:M a) or (subreg:M1 (reg:M2 a)
+   x) rtx's.  Furthermore if it's a subreg rtx M1 is at least one word wide,
+   and a is a multi-word pseudo.  If DEF or USE are hardregs, they are in
+   wordmode, so we don't need to check for further hardregs which would result
+   from wider references.  We are never called with paradoxical subregs.
+
+   This returns:
+   0 for no common bits,
+   1 if DEF and USE exactly cover the same bytes,
+   2 if the DEF only covers a part of the bits of USE
+   3 if the DEF covers more than the bits of the USE, and
+   4 if both are SUBREG's of different size, but have bytes in common.
+   -1 is a special case, for when DEF and USE refer to the same regno, but
+      have for other reasons no bits in common (can only happen with
+      subregs refering to different words, or to words which already were
+      defined for this USE).
+   Furthermore it modifies use->undefined to clear the bits which get defined
+   by DEF (only for cases with partial overlap).
+   I.e. if bit 1 is set for the result != -1, the USE was completely covered,
+   otherwise a test is needed to track the already defined bytes.  */
+
+static int
+defuse_overlap_p_1 (def, use)
+     rtx def;
+     struct curr_use *use;
+{
+  int mode = 0;
+  if (def == use->x)
+    return 1;
+  if (!def)
+    return 0;
+  if (GET_CODE (def) == SUBREG)
+    {
+      if (REGNO (SUBREG_REG (def)) != use->regno)
+	return 0;
+      mode |= 1;
+    }
+  else if (REGNO (def) != use->regno)
+    return 0;
+  if (GET_CODE (use->x) == SUBREG)
+    mode |= 2;
+  switch (mode)
+    {
+      case 0: /* REG, REG */
+	return 1;
+      case 1: /* SUBREG, REG */
+	{
+	  unsigned HOST_WIDE_INT old_u = use->undefined;
+	  use->undefined &= ~ rtx_to_undefined (def);
+	  return (old_u != use->undefined) ? 2 : -1;
+	}
+      case 2: /* REG, SUBREG */
+	return 3;
+      case 3: /* SUBREG, SUBREG */
+	if (GET_MODE_SIZE (GET_MODE (def)) == GET_MODE_SIZE (GET_MODE (use->x)))
+	  /* If the size of both things is the same, the subreg's overlap
+	     if they refer to the same word.  */
+	  if (SUBREG_BYTE (def) == SUBREG_BYTE (use->x))
+	    return 1;
+	/* Now the more difficult part: the same regno is refered, but the
+	   sizes of the references or the words differ.  E.g.
+           (subreg:SI (reg:CDI a) 0) and (subreg:DI (reg:CDI a) 2) do not
+	   overlap, wereas the latter overlaps with (subreg:SI (reg:CDI a) 3).
+	   */
+	{
+	  unsigned HOST_WIDE_INT old_u;
+	  int b1, e1, b2, e2;
+	  unsigned int bl1, bl2;
+	  bl1 = rtx_to_bits (def);
+	  bl2 = rtx_to_bits (use->x);
+	  b1 = BYTE_BEGIN (bl1);
+	  b2 = BYTE_BEGIN (bl2);
+	  e1 = b1 + BYTE_LENGTH (bl1) - 1;
+	  e2 = b2 + BYTE_LENGTH (bl2) - 1;
+	  if (b1 > e2 || b2 > e1)
+	    return -1;
+	  old_u = use->undefined;
+	  use->undefined &= ~ rtx_to_undefined (def);
+	  return (old_u != use->undefined) ? 4 : -1;
+	}
+      default:
+        abort ();
+    }
+}
+
+/* Macro for the common case of either def and use having the same rtx,
+   or based on different regnos.  */
+#define defuse_overlap_p(def, use) \
+  ((def) == (use)->x ? 1 : \
+     (REGNO (GET_CODE (def) == SUBREG \
+	     ? SUBREG_REG (def) : def) != use->regno \
+      ? 0 : defuse_overlap_p_1 (def, use)))
+
+
+/* The use USE flows into INSN (backwards).  Determine INSNs effect on it,
+   and return nonzero, if (parts of) that USE are also live before it.
+   This also notes conflicts between the USE and all DEFS in that insn,
+   and modifies the undefined bits of USE in case parts of it were set in
+   this insn.  */
+
+static int
+live_out_1 (df, use, insn)
+     struct df *df ATTRIBUTE_UNUSED;
+     struct curr_use *use;
+     rtx insn;
+{
+  int defined = 0;
+  int uid = INSN_UID (insn);
+  struct web_part *wp = use->wp;
+
+  /* Mark, that this insn needs this webpart live.  */
+  visit_trace[uid].wp = wp;
+  visit_trace[uid].undefined = use->undefined;
+
+  if (INSN_P (insn))
+    {
+      unsigned int source_regno = ~0;
+      unsigned int regno = use->regno;
+      unsigned HOST_WIDE_INT orig_undef = use->undefined;
+      unsigned HOST_WIDE_INT final_undef = use->undefined;
+      rtx s = NULL;
+      unsigned int n, num_defs = insn_df[uid].num_defs;
+      struct ref **defs = insn_df[uid].defs;
+
+      /* We want to access the root webpart.  */
+      wp = find_web_part (wp);
+      if (GET_CODE (insn) == CALL_INSN)
+	wp->crosses_call = 1;
+      else if (copy_insn_p (insn, &s, NULL))
+	source_regno = REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s);
+
+      /* Look at all DEFS in this insn.  */
+      for (n = 0; n < num_defs; n++)
+	{
+	  struct ref *ref = defs[n];
+	  int lap;
+
+	  /* Reset the undefined bits for each iteration, in case this
+	     insn has more than one set, and one of them sets this regno.
+	     But still the original undefined part conflicts with the other
+	     sets.  */
+	  use->undefined = orig_undef;
+	  if ((lap = defuse_overlap_p (DF_REF_REG (ref), use)) != 0)
+	    {
+	      if (lap == -1)
+		  /* Same regnos but non-overlapping or already defined bits,
+		     so ignore this DEF, or better said make the yet undefined
+		     part and this DEF conflicting.  */
+		{
+		  unsigned HOST_WIDE_INT undef;
+		  undef = use->undefined;
+		  while (undef)
+		    bitmap_set_bit (undef_to_bitmap (wp, &undef),
+				    DF_REF_ID (ref));
+		  continue;
+		}
+	      if ((lap & 1) != 0)
+		  /* The current DEF completely covers the USE, so we can
+		     stop traversing the code looking for further DEFs.  */
+		defined = 1;
+	      else
+		  /* We have a partial overlap.  */
+		{
+		  final_undef &= use->undefined;
+		  if (final_undef == 0)
+		    /* Now the USE is completely defined, which means, that
+		       we can stop looking for former DEFs.  */
+		    defined = 1;
+		  /* If this is a partial overlap, which left some bits
+		     in USE undefined, we normally would need to create
+		     conflicts between that undefined part and the part of
+		     this DEF which overlapped with some of the formerly
+		     undefined bits.  We don't need to do this, because both
+		     parts of this DEF (that which overlaps, and that which
+		     doesn't) are written together in this one DEF, and can
+		     not be colored in a way which would conflict with
+		     the USE.  This is only true for partial overlap,
+		     because only then the DEF and USE have bits in common,
+		     which makes the DEF move, if the USE moves, making them
+		     aligned.
+		     If they have no bits in common (lap == -1), they are
+		     really independent.  Therefore we there made a
+		     conflict above.  */
+		}
+	      /* This is at least a partial overlap, so we need to union
+		 the web parts.  */
+	      wp = union_web_parts (wp, &web_parts[DF_REF_ID (ref)]);
+	    }
+	  else
+	    {
+	      /* The DEF and the USE don't overlap at all, different
+		 regnos.  I.e. make conflicts between the undefined bits,
+	         and that DEF.  */
+	      unsigned HOST_WIDE_INT undef = use->undefined;
+
+	      if (regno == source_regno)
+		/* This triggers only, when this was a copy insn and the
+		   source is at least a part of the USE currently looked at.
+		   In this case only the bits of the USE conflict with the
+		   DEF, which are not covered by the source of this copy
+		   insn, and which are still undefined.  I.e. in the best
+		   case (the whole reg being the source), _no_ conflicts
+		   between that USE and this DEF (the target of the move)
+		   are created by this insn (though they might be by
+		   others).  This is a super case of the normal copy insn
+		   only between full regs.  */
+		{
+		  undef &= ~ rtx_to_undefined (s);
+		}
+	      if (undef)
+		{
+		  /*struct web_part *cwp;
+		    cwp = find_web_part (&web_parts[DF_REF_ID
+		    (ref)]);*/
+
+		  /* TODO: somehow instead of noting the ID of the LINK
+		     use an ID nearer to the root webpart of that LINK.
+		     We can't use the root itself, because we later use the
+		     ID to look at the form (reg or subreg, and if yes,
+		     which subreg) of this conflict.  This means, that we
+		     need to remember in the root an ID for each form, and
+		     maintaining this, when merging web parts.  This makes
+		     the bitmaps smaller.  */
+		  do
+		    bitmap_set_bit (undef_to_bitmap (wp, &undef),
+				    DF_REF_ID (ref));
+		  while (undef);
+		}
+	    }
+	}
+      if (defined)
+	use->undefined = 0;
+      else
+	{
+	  /* If this insn doesn't completely define the USE, increment also
+	     it's spanned deaths count (if this insn contains a death). */
+	  if (uid >= death_insns_max_uid)
+	    abort ();
+	  if (TEST_BIT (insns_with_deaths, uid))
+	    wp->spanned_deaths++;
+	  use->undefined = final_undef;
+	}
+    }
+
+  return !defined;
+}
+
+/* Same as live_out_1() (actually calls it), but caches some information.
+   E.g. if we reached this INSN with the current regno already, and the
+   current undefined bits are a subset of those as we came here, we
+   simply connect the web parts of the USE, and the one cached for this
+   INSN, and additionally return zero, indicating we don't need to traverse
+   this path any longer (all effect were already seen, as we first reached
+   this insn).  */
+
+static inline int
+live_out (df, use, insn)
+     struct df *df;
+     struct curr_use *use;
+     rtx insn;
+{
+  unsigned int uid = INSN_UID (insn);
+  if (visit_trace[uid].wp
+      && DF_REF_REGNO (visit_trace[uid].wp->ref) == use->regno
+      && (use->undefined & ~visit_trace[uid].undefined) == 0)
+    {
+      union_web_parts (visit_trace[uid].wp, use->wp);
+      /* Don't search any further, as we already were here with this regno. */
+      return 0;
+    }
+  else
+    return live_out_1 (df, use, insn);
+}
+
+/* The current USE reached a basic block head.  The edge E is one
+   of the predecessors edges.  This evaluates the effect of the predecessor
+   block onto the USE, and returns the next insn, which should be looked at.
+   This either is the last insn of that pred. block, or the first one.
+   The latter happens, when the pred. block has no possible effect on the
+   USE, except for conflicts.  In that case, it's remembered, that the USE
+   is live over that whole block, and it's skipped.  Otherwise we simply
+   continue with the last insn of the block.
+
+   This also determines the effects of abnormal edges, and remembers
+   which uses are live at the end of that basic block.  */
+
+static rtx
+live_in_edge (df, use, e)
+     struct df *df;
+     struct curr_use *use;
+     edge e;
+{
+  struct ra_bb_info *info_pred;
+  rtx next_insn;
+  /* Call used hard regs die over an exception edge, ergo
+     they don't reach the predecessor block, so ignore such
+     uses.  And also don't set the live_over_abnormal flag
+     for them.  */
+  if ((e->flags & EDGE_EH) && use->regno < FIRST_PSEUDO_REGISTER
+      && call_used_regs[use->regno])
+    return NULL_RTX;
+  if (e->flags & EDGE_ABNORMAL)
+    use->live_over_abnormal = 1;
+  bitmap_set_bit (live_at_end[e->src->index], DF_REF_ID (use->wp->ref));
+  info_pred = (struct ra_bb_info *) e->src->aux;
+  next_insn = e->src->end;
+
+  /* If the last insn of the pred. block doesn't completely define the
+     current use, we need to check the block.  */
+  if (live_out (df, use, next_insn))
+    {
+      /* If the current regno isn't mentioned anywhere in the whole block,
+	 and the complete use is still undefined...  */
+      if (!bitmap_bit_p (info_pred->regnos_mentioned, use->regno)
+	  && (rtx_to_undefined (use->x) & ~use->undefined) == 0)
+	{
+	  /* ...we can hop over the whole block and defer conflict
+	     creation to later.  */
+	  bitmap_set_bit (info_pred->live_throughout,
+			  DF_REF_ID (use->wp->ref));
+	  next_insn = e->src->head;
+	}
+      return next_insn;
+    }
+  else
+    return NULL_RTX;
+}
+
+/* USE flows into the end of the insns preceding INSN.  Determine
+   their effects (in live_out()) and possibly loop over the preceding INSN,
+   or call itself recursively on a basic block border.  When a topleve
+   call of this function returns the USE is completely analyzed.  I.e.
+   its def-use chain (at least) is built, possibly connected with other
+   def-use chains, and all defs during that chain are noted.  */
+
+static void
+live_in (df, use, insn)
+     struct df *df;
+     struct curr_use *use;
+     rtx insn;
+{
+  unsigned int loc_vpass = visited_pass;
+
+  /* Note, that, even _if_ we are called with use->wp a root-part, this might
+     become non-root in the for() loop below (due to live_out() unioning
+     it).  So beware, not to change use->wp in a way, for which only root-webs
+     are allowed.  */
+  while (1)
+    {
+      int uid = INSN_UID (insn);
+      basic_block bb = BLOCK_FOR_INSN (insn);
+      number_seen[uid]++;
+
+      /* We want to be as fast as possible, so explicitely write
+	 this loop.  */
+      for (insn = PREV_INSN (insn); insn && !INSN_P (insn);
+	   insn = PREV_INSN (insn))
+	;
+      if (!insn)
+	return;
+      if (bb != BLOCK_FOR_INSN (insn))
+	{
+	  edge e;
+	  unsigned HOST_WIDE_INT undef = use->undefined;
+	  struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
+	  if ((e = bb->pred) == NULL)
+	    return;
+	  /* We now check, if we already traversed the predecessors of this
+	     block for the current pass and the current set of undefined
+	     bits.  If yes, we don't need to check the predecessors again.
+	     So, conceptually this information is tagged to the first
+	     insn of a basic block.  */
+	  if (info->pass == loc_vpass && (undef & ~info->undefined) == 0)
+	    return;
+	  info->pass = loc_vpass;
+	  info->undefined = undef;
+	  /* All but the last predecessor are handled recursively.  */
+	  for (; e->pred_next; e = e->pred_next)
+	    {
+	      insn = live_in_edge (df, use, e);
+	      if (insn)
+		live_in (df, use, insn);
+	      use->undefined = undef;
+	    }
+	  insn = live_in_edge (df, use, e);
+	  if (!insn)
+	    return;
+	}
+      else if (!live_out (df, use, insn))
+	return;
+    }
+}
+
+/* Determine all regnos which are mentioned in a basic block, in an
+   interesting way.  Interesting here means either in a def, or as the
+   source of a move insn.  We only look at insns added since the last
+   pass.  */
+
+static void
+update_regnos_mentioned ()
+{
+  int last_uid = last_max_uid;
+  rtx insn;
+  basic_block bb;
+  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    if (INSN_P (insn))
+      {
+	/* Don't look at old insns.  */
+	if (INSN_UID (insn) < last_uid)
+	  {
+	    /* XXX We should also remember moves over iterations (we already
+	       save the cache, but not the movelist).  */
+	    if (copy_insn_p (insn, NULL, NULL))
+	      remember_move (insn);
+	  }
+	else if ((bb = BLOCK_FOR_INSN (insn)) != NULL)
+	  {
+	    rtx source;
+	    struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
+	    bitmap mentioned = info->regnos_mentioned;
+	    struct df_link *link;
+	    if (copy_insn_p (insn, &source, NULL))
+	      {
+		remember_move (insn);
+		bitmap_set_bit (mentioned,
+				REGNO (GET_CODE (source) == SUBREG
+				       ? SUBREG_REG (source) : source));
+	      }
+	    for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
+	      if (link->ref)
+		bitmap_set_bit (mentioned, DF_REF_REGNO (link->ref));
+	  }
+      }
+}
+
+/* Handle the uses which reach a block end, but were defered due
+   to it's regno not being mentioned in that block.  This adds the
+   remaining conflicts and updates also the crosses_call and
+   spanned_deaths members.  */
+
+static void
+livethrough_conflicts_bb (bb)
+     basic_block bb;
+{
+  struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
+  rtx insn;
+  bitmap all_defs;
+  int first, use_id;
+  unsigned int deaths = 0;
+  unsigned int contains_call = 0;
+
+  /* If there are no defered uses, just return.  */
+  if ((first = bitmap_first_set_bit (info->live_throughout)) < 0)
+    return;
+
+  /* First collect the IDs of all defs, count the number of death
+     containing insns, and if there's some call_insn here.  */
+  all_defs = BITMAP_XMALLOC ();
+  for (insn = bb->head; insn; insn = NEXT_INSN (insn))
+    {
+      if (INSN_P (insn))
+	{
+	  struct ra_insn_info info = insn_df[INSN_UID (insn)];
+	  unsigned int n;
+	  for (n = 0; n < info.num_defs; n++)
+	    bitmap_set_bit (all_defs, DF_REF_ID (info.defs[n]));
+	  if (TEST_BIT (insns_with_deaths, INSN_UID (insn)))
+	    deaths++;
+	  if (GET_CODE (insn) == CALL_INSN)
+	    contains_call = 1;
+	}
+      if (insn == bb->end)
+	break;
+    }
+
+  /* And now, if we have found anything, make all live_through
+     uses conflict with all defs, and update their other members.  */
+  if (deaths > 0 || bitmap_first_set_bit (all_defs) >= 0)
+    EXECUTE_IF_SET_IN_BITMAP (info->live_throughout, first, use_id,
+      {
+        struct web_part *wp = &web_parts[df->def_id + use_id];
+        unsigned int bl = rtx_to_bits (DF_REF_REG (wp->ref));
+        bitmap conflicts;
+        wp = find_web_part (wp);
+        wp->spanned_deaths += deaths;
+	wp->crosses_call |= contains_call;
+        conflicts = get_sub_conflicts (wp, bl);
+        bitmap_operation (conflicts, conflicts, all_defs, BITMAP_IOR);
+      });
+
+  BITMAP_XFREE (all_defs);
+}
+
+/* Allocate the per basic block info for traversing the insn stream for
+   building live ranges.  */
+
+static void
+init_bb_info ()
+{
+  basic_block bb;
+  FOR_ALL_BB (bb)
+    {
+      struct ra_bb_info *info =
+	(struct ra_bb_info *) xcalloc (1, sizeof *info);
+      info->regnos_mentioned = BITMAP_XMALLOC ();
+      info->live_throughout = BITMAP_XMALLOC ();
+      info->old_aux = bb->aux;
+      bb->aux = (void *) info;
+    }
+}
+
+/* Free that per basic block info.  */
+
+static void
+free_bb_info ()
+{
+  basic_block bb;
+  FOR_ALL_BB (bb)
+    {
+      struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
+      BITMAP_XFREE (info->regnos_mentioned);
+      BITMAP_XFREE (info->live_throughout);
+      bb->aux = info->old_aux;
+      free (info);
+    }
+}
+
+/* Toplevel function for the first part of this file.
+   Connect web parts, thereby implicitely building webs, and remember
+   their conflicts.  */
+
+static void
+build_web_parts_and_conflicts (df)
+     struct df *df;
+{
+  struct df_link *link;
+  struct curr_use use;
+  basic_block bb;
+
+  number_seen = (int *) xcalloc (get_max_uid (), sizeof (int));
+  visit_trace = (struct visit_trace *) xcalloc (get_max_uid (),
+						sizeof (visit_trace[0]));
+  update_regnos_mentioned ();
+
+  /* Here's the main loop.
+     It goes through all insn's, connects web parts along the way, notes
+     conflicts between webparts, and remembers move instructions.  */
+  visited_pass = 0;
+  for (use.regno = 0; use.regno < (unsigned int)max_regno; use.regno++)
+    if (use.regno >= FIRST_PSEUDO_REGISTER || !fixed_regs[use.regno])
+      for (link = df->regs[use.regno].uses; link; link = link->next)
+        if (link->ref)
+	  {
+	    struct ref *ref = link->ref;
+	    rtx insn = DF_REF_INSN (ref);
+	    /* Only recheck marked or new uses, or uses from hardregs.  */
+	    if (use.regno >= FIRST_PSEUDO_REGISTER
+		&& DF_REF_ID (ref) < last_use_id
+		&& !TEST_BIT (last_check_uses, DF_REF_ID (ref)))
+	      continue;
+	    use.wp = &web_parts[df->def_id + DF_REF_ID (ref)];
+	    use.x = DF_REF_REG (ref);
+	    use.live_over_abnormal = 0;
+	    use.undefined = rtx_to_undefined (use.x);
+	    visited_pass++;
+	    live_in (df, &use, insn);
+	    if (use.live_over_abnormal)
+	      SET_BIT (live_over_abnormal, DF_REF_ID (ref));
+	  }
+
+  dump_number_seen ();
+  FOR_ALL_BB (bb)
+    {
+      struct ra_bb_info *info = (struct ra_bb_info *) bb->aux;
+      livethrough_conflicts_bb (bb);
+      bitmap_zero (info->live_throughout);
+      info->pass = 0;
+    }
+  free (visit_trace);
+  free (number_seen);
+}
+
+/* Here we look per insn, for DF references being in uses _and_ defs.
+   This means, in the RTL a (REG xx) expression was seen as a
+   read/modify/write, as happens for (set (subreg:SI (reg:DI xx)) (...))
+   e.g.  Our code has created two webs for this, as it should.  Unfortunately,
+   as the REG reference is only one time in the RTL we can't color
+   both webs different (arguably this also would be wrong for a real
+   read-mod-write instruction), so we must reconnect such webs.  */
+
+static void
+connect_rmw_web_parts (df)
+     struct df *df;
+{
+  unsigned int i;
+
+  for (i = 0; i < df->use_id; i++)
+    {
+      struct web_part *wp1 = &web_parts[df->def_id + i];
+      rtx reg;
+      struct df_link *link;
+      if (!wp1->ref)
+	continue;
+      /* If it's an uninitialized web, we don't want to connect it to others,
+	 as the read cycle in read-mod-write had probably no effect.  */
+      if (find_web_part (wp1) >= &web_parts[df->def_id])
+	continue;
+      reg = DF_REF_REAL_REG (wp1->ref);
+      link = DF_INSN_DEFS (df, DF_REF_INSN (wp1->ref));
+      for (; link; link = link->next)
+        if (reg == DF_REF_REAL_REG (link->ref))
+	  {
+	    struct web_part *wp2 = &web_parts[DF_REF_ID (link->ref)];
+	    union_web_parts (wp1, wp2);
+	  }
+    }
+}
+
+/* Deletes all hardregs from *S which are not allowed for MODE.  */
+
+static void
+prune_hardregs_for_mode (s, mode)
+     HARD_REG_SET *s;
+     enum machine_mode mode;
+{
+  AND_HARD_REG_SET (*s, hardregs_for_mode[(int) mode]);
+}
+
+/* Initialize the members of a web, which are deducible from REG.  */
+
+static void
+init_one_web_common (web, reg)
+     struct web *web;
+     rtx reg;
+{
+  if (GET_CODE (reg) != REG)
+    abort ();
+  /* web->id isn't initialized here.  */
+  web->regno = REGNO (reg);
+  web->orig_x = reg;
+  if (!web->dlink)
+    {
+      web->dlink = (struct dlist *) ra_calloc (sizeof (struct dlist));
+      DLIST_WEB (web->dlink) = web;
+    }
+  /* XXX
+     the former (superunion) doesn't constrain the graph enough. E.g.
+     on x86 QImode _requires_ QI_REGS, but as alternate class usually
+     GENERAL_REGS is given.  So the graph is not constrained enough,
+     thinking it has more freedom then it really has, which leads
+     to repeated spill tryings.  OTOH the latter (only using preferred
+     class) is too constrained, as normally (e.g. with all SImode
+     pseudos), they can be allocated also in the alternate class.
+     What we really want, are the _exact_ hard regs allowed, not
+     just a class.  Later.  */
+  /*web->regclass = reg_class_superunion
+		    [reg_preferred_class (web->regno)]
+		    [reg_alternate_class (web->regno)];*/
+  /*web->regclass = reg_preferred_class (web->regno);*/
+  web->regclass = reg_class_subunion
+    [reg_preferred_class (web->regno)] [reg_alternate_class (web->regno)];
+  web->regclass = reg_preferred_class (web->regno);
+  if (web->regno < FIRST_PSEUDO_REGISTER)
+    {
+      web->color = web->regno;
+      put_web (web, PRECOLORED);
+      web->num_conflicts = UINT_MAX;
+      web->add_hardregs = 0;
+      CLEAR_HARD_REG_SET (web->usable_regs);
+      SET_HARD_REG_BIT (web->usable_regs, web->regno);
+      web->num_freedom = 1;
+    }
+  else
+    {
+      HARD_REG_SET alternate;
+      web->color = -1;
+      put_web (web, INITIAL);
+      /* add_hardregs is wrong in multi-length classes, e.g.
+	 using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
+	 where, if it finally is allocated to GENERAL_REGS it needs two,
+	 if allocated to FLOAT_REGS only one hardreg.  XXX */
+      web->add_hardregs =
+	CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
+      web->num_conflicts = 0 * web->add_hardregs;
+      COPY_HARD_REG_SET (web->usable_regs,
+			reg_class_contents[reg_preferred_class (web->regno)]);
+      COPY_HARD_REG_SET (alternate,
+			reg_class_contents[reg_alternate_class (web->regno)]);
+      IOR_HARD_REG_SET (web->usable_regs, alternate);
+      /*IOR_HARD_REG_SET (web->usable_regs,
+			reg_class_contents[reg_alternate_class
+			(web->regno)]);*/
+      AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
+      prune_hardregs_for_mode (&web->usable_regs,
+			       PSEUDO_REGNO_MODE (web->regno));
+#ifdef CLASS_CANNOT_CHANGE_MODE
+      if (web->mode_changed)
+        AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
+			          (int) CLASS_CANNOT_CHANGE_MODE]);
+#endif
+      web->num_freedom = hard_regs_count (web->usable_regs);
+      web->num_freedom -= web->add_hardregs;
+      if (!web->num_freedom)
+	abort();
+    }
+  COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
+}
+
+/* Initializes WEBs members from REG or zero them.  */
+
+static void
+init_one_web (web, reg)
+     struct web *web;
+     rtx reg;
+{
+  memset (web, 0, sizeof (struct web));
+  init_one_web_common (web, reg);
+  web->useless_conflicts = BITMAP_XMALLOC ();
+}
+
+/* WEB is an old web, meaning it came from the last pass, and got a
+   color.  We want to remember some of it's info, so zero only some
+   members.  */
+
+static void
+reinit_one_web (web, reg)
+     struct web *web;
+     rtx reg;
+{
+  web->old_color = web->color + 1;
+  init_one_web_common (web, reg);
+  web->span_deaths = 0;
+  web->spill_temp = 0;
+  web->orig_spill_temp = 0;
+  web->use_my_regs = 0;
+  web->spill_cost = 0;
+  web->was_spilled = 0;
+  web->is_coalesced = 0;
+  web->artificial = 0;
+  web->live_over_abnormal = 0;
+  web->mode_changed = 0;
+  web->move_related = 0;
+  web->in_load = 0;
+  web->target_of_spilled_move = 0;
+  web->num_aliased = 0;
+  if (web->type == PRECOLORED)
+    {
+      web->num_defs = 0;
+      web->num_uses = 0;
+      web->orig_spill_cost = 0;
+    }
+  CLEAR_HARD_REG_SET (web->bias_colors);
+  CLEAR_HARD_REG_SET (web->prefer_colors);
+  web->reg_rtx = NULL;
+  web->stack_slot = NULL;
+  web->pattern = NULL;
+  web->alias = NULL;
+  if (web->moves)
+    abort ();
+  if (!web->useless_conflicts)
+    abort ();
+}
+
+/* Insert and returns a subweb corresponding to REG into WEB (which
+   becomes its super web).  It must not exist already.  */
+
+static struct web *
+add_subweb (web, reg)
+     struct web *web;
+     rtx reg;
+{
+  struct web *w;
+  if (GET_CODE (reg) != SUBREG)
+    abort ();
+  w = (struct web *) xmalloc (sizeof (struct web));
+  /* Copy most content from parent-web.  */
+  *w = *web;
+  /* And initialize the private stuff.  */
+  w->orig_x = reg;
+  w->add_hardregs = CLASS_MAX_NREGS (web->regclass, GET_MODE (reg)) - 1;
+  w->num_conflicts = 0 * w->add_hardregs;
+  w->num_defs = 0;
+  w->num_uses = 0;
+  w->dlink = NULL;
+  w->parent_web = web;
+  w->subreg_next = web->subreg_next;
+  web->subreg_next = w;
+  return w;
+}
+
+/* Similar to add_subweb(), but instead of relying on a given SUBREG,
+   we have just a size and an offset of the subpart of the REG rtx.
+   In difference to add_subweb() this marks the new subweb as artificial.  */
+
+static struct web *
+add_subweb_2 (web, size_word)
+     struct web *web;
+     unsigned int size_word;
+{
+  /* To get a correct mode for the to be produced subreg, we don't want to
+     simply do a mode_for_size() for the mode_class of the whole web.
+     Suppose we deal with a CDImode web, but search for a 8 byte part.
+     Now mode_for_size() would only search in the class MODE_COMPLEX_INT
+     and would find CSImode which probably is not what we want.  Instead
+     we want DImode, which is in a completely other class.  For this to work
+     we instead first search the already existing subwebs, and take
+     _their_ modeclasses as base for a search for ourself.  */
+  rtx ref_rtx = (web->subreg_next ? web->subreg_next : web)->orig_x;
+  unsigned int size = BYTE_LENGTH (size_word) * BITS_PER_UNIT;
+  enum machine_mode mode;
+  mode = mode_for_size (size, GET_MODE_CLASS (GET_MODE (ref_rtx)), 0);
+  if (mode == BLKmode)
+    mode = mode_for_size (size, MODE_INT, 0);
+  if (mode == BLKmode)
+    abort ();
+  web = add_subweb (web, gen_rtx_SUBREG (mode, web->orig_x,
+					 BYTE_BEGIN (size_word)));
+  web->artificial = 1;
+  return web;
+}
+
+/* Initialize all the web parts we are going to need.  */
+
+static void
+init_web_parts (df)
+     struct df *df;
+{
+  int regno;
+  unsigned int no;
+  num_webs = 0;
+  for (no = 0; no < df->def_id; no++)
+    {
+      if (df->defs[no])
+	{
+	  if (no < last_def_id && web_parts[no].ref != df->defs[no])
+	    abort ();
+	  web_parts[no].ref = df->defs[no];
+	  /* Uplink might be set from the last iteration.  */
+	  if (!web_parts[no].uplink)
+	    num_webs++;
+	}
+      else
+	/* The last iteration might have left .ref set, while df_analyse()
+	   removed that ref (due to a removed copy insn) from the df->defs[]
+	   array.  As we don't check for that in realloc_web_parts()
+	   we do that here.  */
+	web_parts[no].ref = NULL;
+    }
+  for (no = 0; no < df->use_id; no++)
+    {
+      if (df->uses[no])
+	{
+	  if (no < last_use_id
+	      && web_parts[no + df->def_id].ref != df->uses[no])
+	    abort ();
+	  web_parts[no + df->def_id].ref = df->uses[no];
+	  if (!web_parts[no + df->def_id].uplink)
+	    num_webs++;
+	}
+      else
+	web_parts[no + df->def_id].ref = NULL;
+    }
+
+  /* We want to have only one web for each precolored register.  */
+  for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+    {
+      struct web_part *r1 = NULL;
+      struct df_link *link;
+      /* Here once was a test, if there is any DEF at all, and only then to
+	 merge all the parts.  This was incorrect, we really also want to have
+	 only one web-part for hardregs, even if there is no explicit DEF.  */
+      /* Link together all defs...  */
+      for (link = df->regs[regno].defs; link; link = link->next)
+        if (link->ref)
+	  {
+	    struct web_part *r2 = &web_parts[DF_REF_ID (link->ref)];
+	    if (!r1)
+	      r1 = r2;
+	    else
+	      r1 = union_web_parts (r1, r2);
+	  }
+      /* ... and all uses.  */
+      for (link = df->regs[regno].uses; link; link = link->next)
+	if (link->ref)
+	  {
+	    struct web_part *r2 = &web_parts[df->def_id
+		                             + DF_REF_ID (link->ref)];
+	    if (!r1)
+	      r1 = r2;
+	    else
+	      r1 = union_web_parts (r1, r2);
+	  }
+    }
+}
+
+/* In case we want to remember the conflict list of a WEB, before adding
+   new conflicts, we copy it here to orig_conflict_list.  */
+
+static void
+copy_conflict_list (web)
+     struct web *web;
+{
+  struct conflict_link *cl;
+  if (web->orig_conflict_list || web->have_orig_conflicts)
+    abort ();
+  web->have_orig_conflicts = 1;
+  for (cl = web->conflict_list; cl; cl = cl->next)
+    {
+      struct conflict_link *ncl;
+      ncl = (struct conflict_link *) ra_alloc (sizeof *ncl);
+      ncl->t = cl->t;
+      ncl->sub = NULL;
+      ncl->next = web->orig_conflict_list;
+      web->orig_conflict_list = ncl;
+      if (cl->sub)
+	{
+	  struct sub_conflict *sl, *nsl;
+	  for (sl = cl->sub; sl; sl = sl->next)
+	    {
+	      nsl = (struct sub_conflict *) ra_alloc (sizeof *nsl);
+	      nsl->s = sl->s;
+	      nsl->t = sl->t;
+	      nsl->next = ncl->sub;
+	      ncl->sub = nsl;
+	    }
+	}
+    }
+}
+
+/* Possibly add an edge from web FROM to TO marking a conflict between
+   those two.  This is one half of marking a complete conflict, which notes
+   in FROM, that TO is a conflict.  Adding TO to FROM's conflicts might
+   make other conflicts superflous, because the current TO overlaps some web
+   already being in conflict with FROM.  In this case the smaller webs are
+   deleted from the conflict list.  Likewise if TO is overlapped by a web
+   already in the list, it isn't added at all.  Note, that this can only
+   happen, if SUBREG webs are involved.  */
+
+static void
+add_conflict_edge (from, to)
+     struct web *from, *to;
+{
+  if (from->type != PRECOLORED)
+    {
+      struct web *pfrom = find_web_for_subweb (from);
+      struct web *pto = find_web_for_subweb (to);
+      struct sub_conflict *sl;
+      struct conflict_link *cl = pfrom->conflict_list;
+      int may_delete = 1;
+
+      /* This can happen when subwebs of one web conflict with each
+	 other.  In live_out_1() we created such conflicts between yet
+	 undefined webparts and defs of parts which didn't overlap with the
+	 undefined bits.  Then later they nevertheless could have merged into
+	 one web, and then we land here.  */
+      if (pfrom == pto)
+	return;
+      if (remember_conflicts && !pfrom->have_orig_conflicts)
+	copy_conflict_list (pfrom);
+      if (!TEST_BIT (sup_igraph, (pfrom->id * num_webs + pto->id)))
+	{
+	  cl = (struct conflict_link *) ra_alloc (sizeof (*cl));
+	  cl->t = pto;
+	  cl->sub = NULL;
+	  cl->next = pfrom->conflict_list;
+	  pfrom->conflict_list = cl;
+	  if (pto->type != SELECT && pto->type != COALESCED)
+	    pfrom->num_conflicts += 1 + pto->add_hardregs;
+          SET_BIT (sup_igraph, (pfrom->id * num_webs + pto->id));
+	  may_delete = 0;
+	}
+      else
+        /* We don't need to test for cl==NULL, because at this point
+	   a cl with cl->t==pto is guaranteed to exist.  */
+        while (cl->t != pto)
+	  cl = cl->next;
+      if (pfrom != from || pto != to)
+	{
+	  /* This is a subconflict which should be added.
+	     If we inserted cl in this invocation, we really need to add this
+	     subconflict.  If we did _not_ add it here, we only add the
+	     subconflict, if cl already had subconflicts, because otherwise
+	     this indicated, that the whole webs already conflict, which
+	     means we are not interested in this subconflict.  */
+	  if (!may_delete || cl->sub != NULL)
+	    {
+	      sl = (struct sub_conflict *) ra_alloc (sizeof (*sl));
+	      sl->s = from;
+	      sl->t = to;
+	      sl->next = cl->sub;
+	      cl->sub = sl;
+	    }
+	}
+      else
+	/* pfrom == from && pto == to means, that we are not interested
+	   anymore in the subconflict list for this pair, because anyway
+	   the whole webs conflict.  */
+	cl->sub = NULL;
+    }
+}
+
+/* Record a conflict between two webs, if we haven't recorded it
+   already.  */
+
+void
+record_conflict (web1, web2)
+     struct web *web1, *web2;
+{
+  unsigned int id1 = web1->id, id2 = web2->id;
+  unsigned int index = igraph_index (id1, id2);
+  /* Trivial non-conflict or already recorded conflict.  */
+  if (web1 == web2 || TEST_BIT (igraph, index))
+    return;
+  if (id1 == id2)
+    abort ();
+  /* As fixed_regs are no targets for allocation, conflicts with them
+     are pointless.  */
+  if ((web1->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web1->regno])
+      || (web2->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web2->regno]))
+    return;
+  /* Conflicts with hardregs, which are not even a candidate
+     for this pseudo are also pointless.  */
+  if ((web1->type == PRECOLORED
+       && ! TEST_HARD_REG_BIT (web2->usable_regs, web1->regno))
+      || (web2->type == PRECOLORED
+	  && ! TEST_HARD_REG_BIT (web1->usable_regs, web2->regno)))
+    return;
+  /* Similar if the set of possible hardregs don't intersect.  This iteration
+     those conflicts are useless (and would make num_conflicts wrong, because
+     num_freedom is calculated from the set of possible hardregs).
+     But in presence of spilling and incremental building of the graph we
+     need to note all uses of webs conflicting with the spilled ones.
+     Because the set of possible hardregs can change in the next round for
+     spilled webs, we possibly have then conflicts with webs which would
+     be excluded now (because then hardregs intersect).  But we actually
+     need to check those uses, and to get hold of them, we need to remember
+     also webs conflicting with this one, although not conflicting in this
+     round because of non-intersecting hardregs.  */
+  if (web1->type != PRECOLORED && web2->type != PRECOLORED
+      && ! hard_regs_intersect_p (&web1->usable_regs, &web2->usable_regs))
+    {
+      struct web *p1 = find_web_for_subweb (web1);
+      struct web *p2 = find_web_for_subweb (web2);
+      /* We expect these to be rare enough to justify bitmaps.  And because
+         we have only a special use for it, we note only the superwebs.  */
+      bitmap_set_bit (p1->useless_conflicts, p2->id);
+      bitmap_set_bit (p2->useless_conflicts, p1->id);
+      return;
+    }
+  SET_BIT (igraph, index);
+  add_conflict_edge (web1, web2);
+  add_conflict_edge (web2, web1);
+}
+
+/* For each web W this produces the missing subwebs Wx, such that it's
+   possible to exactly specify (W-Wy) for all already existing subwebs Wy.  */
+
+static void
+build_inverse_webs (web)
+     struct web *web;
+{
+  struct web *sweb = web->subreg_next;
+  unsigned HOST_WIDE_INT undef;
+
+  undef = rtx_to_undefined (web->orig_x);
+  for (; sweb; sweb = sweb->subreg_next)
+    /* Only create inverses of non-artificial webs.  */
+    if (!sweb->artificial)
+      {
+	unsigned HOST_WIDE_INT bits;
+	bits = undef & ~ rtx_to_undefined (sweb->orig_x);
+	while (bits)
+	  {
+	    unsigned int size_word = undef_to_size_word (web->orig_x, &bits);
+	    if (!find_subweb_2 (web, size_word))
+	      add_subweb_2 (web, size_word);
+	  }
+      }
+}
+
+/* Copies the content of WEB to a new one, and link it into WL.
+   Used for consistency checking.  */
+
+static void
+copy_web (web, wl)
+     struct web *web;
+     struct web_link **wl;
+{
+  struct web *cweb = (struct web *) xmalloc (sizeof *cweb);
+  struct web_link *link = (struct web_link *) ra_alloc (sizeof *link);
+  link->next = *wl;
+  *wl = link;
+  link->web = cweb;
+  *cweb = *web;
+}
+
+/* Given a list of webs LINK, compare the content of the webs therein
+   with the global webs of the same ID.  For consistency checking.  */
+
+static void
+compare_and_free_webs (link)
+     struct web_link **link;
+{
+  struct web_link *wl;
+  for (wl = *link; wl; wl = wl->next)
+    {
+      struct web *web1 = wl->web;
+      struct web *web2 = ID2WEB (web1->id);
+      if (web1->regno != web2->regno
+	  || web1->crosses_call != web2->crosses_call
+	  || web1->live_over_abnormal != web2->live_over_abnormal
+	  || web1->mode_changed != web2->mode_changed
+	  || !rtx_equal_p (web1->orig_x, web2->orig_x)
+	  || web1->type != web2->type
+	  /* Only compare num_defs/num_uses with non-hardreg webs.
+	     E.g. the number of uses of the framepointer changes due to
+	     inserting spill code.  */
+	  || (web1->type != PRECOLORED &&
+	      (web1->num_uses != web2->num_uses
+	       || web1->num_defs != web2->num_defs)))
+	abort ();
+      if (web1->type != PRECOLORED)
+	{
+	  unsigned int i;
+	  for (i = 0; i < web1->num_defs; i++)
+	    if (web1->defs[i] != web2->defs[i])
+	      abort ();
+	  for (i = 0; i < web1->num_uses; i++)
+	    if (web1->uses[i] != web2->uses[i])
+	      abort ();
+	}
+      if (web1->type == PRECOLORED)
+	{
+	  if (web1->defs)
+	    free (web1->defs);
+	  if (web1->uses)
+	    free (web1->uses);
+	}
+      free (web1);
+    }
+  *link = NULL;
+}
+
+/* Setup and fill uses[] and defs[] arrays of the webs.  */
+
+static void
+init_webs_defs_uses ()
+{
+  struct dlist *d;
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      unsigned int def_i, use_i;
+      struct df_link *link;
+      if (web->old_web)
+	continue;
+      if (web->type == PRECOLORED)
+	{
+	  web->num_defs = web->num_uses = 0;
+	  continue;
+	}
+      if (web->num_defs)
+        web->defs = (struct ref **) xmalloc (web->num_defs *
+					     sizeof (web->defs[0]));
+      if (web->num_uses)
+        web->uses = (struct ref **) xmalloc (web->num_uses *
+					     sizeof (web->uses[0]));
+      def_i = use_i = 0;
+      for (link = web->temp_refs; link; link = link->next)
+	{
+	  if (DF_REF_REG_DEF_P (link->ref))
+	    web->defs[def_i++] = link->ref;
+	  else
+	    web->uses[use_i++] = link->ref;
+	}
+      web->temp_refs = NULL;
+      if (def_i != web->num_defs || use_i != web->num_uses)
+	abort ();
+    }
+}
+
+/* Called by parts_to_webs().  This creates (or recreates) the webs (and
+   subwebs) from web parts, gives them IDs (only to super webs), and sets
+   up use2web and def2web arrays.  */
+
+static unsigned int
+parts_to_webs_1 (df, copy_webs, all_refs)
+     struct df *df;
+     struct web_link **copy_webs;
+     struct df_link *all_refs;
+{
+  unsigned int i;
+  unsigned int webnum;
+  unsigned int def_id = df->def_id;
+  unsigned int use_id = df->use_id;
+  struct web_part *wp_first_use = &web_parts[def_id];
+
+  /* For each root web part: create and initialize a new web,
+     setup def2web[] and use2web[] for all defs and uses, and
+     id2web for all new webs.  */
+
+  webnum = 0;
+  for (i = 0; i < def_id + use_id; i++)
+    {
+      struct web *web, *subweb;
+      struct web_part *wp = &web_parts[i];
+      struct ref *ref = wp->ref;
+      unsigned int ref_id;
+      rtx reg;
+      if (!ref)
+	continue;
+      ref_id = i;
+      if (i >= def_id)
+	ref_id -= def_id;
+      all_refs[i].ref = ref;
+      reg = DF_REF_REG (ref);
+      if (! wp->uplink)
+	{
+	  /* If we have a web part root, create a new web.  */
+	  unsigned int newid = ~0U;
+	  unsigned int old_web = 0;
+
+	  /* In the first pass, there are no old webs, so unconditionally
+	     allocate a new one.  */
+	  if (ra_pass == 1)
+	    {
+	      web = (struct web *) xmalloc (sizeof (struct web));
+	      newid = last_num_webs++;
+	      init_one_web (web, GET_CODE (reg) == SUBREG
+			         ? SUBREG_REG (reg) : reg);
+	    }
+	  /* Otherwise, we look for an old web.  */
+	  else
+	    {
+	      /* Remember, that use2web == def2web + def_id.
+		 Ergo is def2web[i] == use2web[i - def_id] for i >= def_id.
+		 So we only need to look into def2web[] array.
+		 Try to look at the web, which formerly belonged to this
+		 def (or use).  */
+	      web = def2web[i];
+	      /* Or which belonged to this hardreg.  */
+	      if (!web && DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER)
+		web = hardreg2web[DF_REF_REGNO (ref)];
+	      if (web)
+		{
+		  /* If we found one, reuse it.  */
+		  web = find_web_for_subweb (web);
+		  remove_list (web->dlink, &WEBS(INITIAL));
+		  old_web = 1;
+		  copy_web (web, copy_webs);
+		}
+	      else
+		{
+		  /* Otherwise use a new one.  First from the free list.  */
+		  if (WEBS(FREE))
+		    web = DLIST_WEB (pop_list (&WEBS(FREE)));
+		  else
+		    {
+		      /* Else allocate a new one.  */
+		      web = (struct web *) xmalloc (sizeof (struct web));
+		      newid = last_num_webs++;
+		    }
+		}
+	      /* The id is zeroed in init_one_web().  */
+	      if (newid == ~0U)
+		newid = web->id;
+	      if (old_web)
+		reinit_one_web (web, GET_CODE (reg) == SUBREG
+				     ? SUBREG_REG (reg) : reg);
+	      else
+		init_one_web (web, GET_CODE (reg) == SUBREG
+				   ? SUBREG_REG (reg) : reg);
+	      web->old_web = (old_web && web->type != PRECOLORED) ? 1 : 0;
+	    }
+	  web->span_deaths = wp->spanned_deaths;
+	  web->crosses_call = wp->crosses_call;
+	  web->id = newid;
+	  web->temp_refs = NULL;
+	  webnum++;
+	  if (web->regno < FIRST_PSEUDO_REGISTER && !hardreg2web[web->regno])
+	    hardreg2web[web->regno] = web;
+	  else if (web->regno < FIRST_PSEUDO_REGISTER
+		   && hardreg2web[web->regno] != web)
+	    abort ();
+	}
+
+      /* If this reference already had a web assigned, we are done.
+         This test better is equivalent to the web being an old web.
+         Otherwise something is screwed.  (This is tested)  */
+      if (def2web[i] != NULL)
+	{
+	  web = def2web[i];
+	  web = find_web_for_subweb (web);
+	  /* But if this ref includes a mode change, or was a use live
+	     over an abnormal call, set appropriate flags in the web.  */
+	  if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0
+	      && web->regno >= FIRST_PSEUDO_REGISTER)
+	    web->mode_changed = 1;
+	  if (i >= def_id
+	      && TEST_BIT (live_over_abnormal, ref_id))
+	    web->live_over_abnormal = 1;
+	  /* And check, that it's not a newly allocated web.  This would be
+	     an inconsistency.  */
+	  if (!web->old_web || web->type == PRECOLORED)
+	    abort ();
+	  continue;
+	}
+      /* In case this was no web part root, we need to initialize WEB
+	 from the ref2web array belonging to the root.  */
+      if (wp->uplink)
+	{
+	  struct web_part *rwp = find_web_part (wp);
+	  unsigned int j = DF_REF_ID (rwp->ref);
+	  if (rwp < wp_first_use)
+	    web = def2web[j];
+	  else
+	    web = use2web[j];
+	  web = find_web_for_subweb (web);
+	}
+
+      /* Remember all references for a web in a single linked list.  */
+      all_refs[i].next = web->temp_refs;
+      web->temp_refs = &all_refs[i];
+
+      /* And the test, that if def2web[i] was NULL above, that we are _not_
+	 an old web.  */
+      if (web->old_web && web->type != PRECOLORED)
+	abort ();
+
+      /* Possible create a subweb, if this ref was a subreg.  */
+      if (GET_CODE (reg) == SUBREG)
+	{
+	  subweb = find_subweb (web, reg);
+	  if (!subweb)
+	    {
+	      subweb = add_subweb (web, reg);
+	      if (web->old_web)
+		abort ();
+	    }
+	}
+      else
+	subweb = web;
+
+      /* And look, if the ref involves an invalid mode change.  */
+      if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0
+	  && web->regno >= FIRST_PSEUDO_REGISTER)
+	web->mode_changed = 1;
+
+      /* Setup def2web, or use2web, and increment num_defs or num_uses.  */
+      if (i < def_id)
+	{
+	  /* Some sanity checks.  */
+	  if (ra_pass > 1)
+	    {
+	      struct web *compare = def2web[i];
+	      if (i < last_def_id)
+		{
+		  if (web->old_web && compare != subweb)
+		    abort ();
+		}
+	      if (!web->old_web && compare)
+		abort ();
+	      if (compare && compare != subweb)
+		abort ();
+	    }
+	  def2web[i] = subweb;
+	  web->num_defs++;
+	}
+      else
+	{
+	  if (ra_pass > 1)
+	    {
+	      struct web *compare = use2web[ref_id];
+	      if (ref_id < last_use_id)
+		{
+		  if (web->old_web && compare != subweb)
+		    abort ();
+		}
+	      if (!web->old_web && compare)
+		abort ();
+	      if (compare && compare != subweb)
+		abort ();
+	    }
+	  use2web[ref_id] = subweb;
+	  web->num_uses++;
+	  if (TEST_BIT (live_over_abnormal, ref_id))
+	    web->live_over_abnormal = 1;
+	}
+    }
+
+  /* We better now have exactly as many webs as we had web part roots.  */
+  if (webnum != num_webs)
+    abort ();
+
+  return webnum;
+}
+
+/* This builds full webs out of web parts, without relating them to each
+   other (i.e. without creating the conflict edges).  */
+
+static void
+parts_to_webs (df)
+     struct df *df;
+{
+  unsigned int i;
+  unsigned int webnum;
+  struct web_link *copy_webs = NULL;
+  struct dlist *d;
+  struct df_link *all_refs;
+  num_subwebs = 0;
+
+  /* First build webs and ordinary subwebs.  */
+  all_refs = (struct df_link *) xcalloc (df->def_id + df->use_id,
+					 sizeof (all_refs[0]));
+  webnum = parts_to_webs_1 (df, &copy_webs, all_refs);
+
+  /* Setup the webs for hardregs which are still missing (weren't
+     mentioned in the code).  */
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (!hardreg2web[i])
+      {
+	struct web *web = (struct web *) xmalloc (sizeof (struct web));
+	init_one_web (web, gen_rtx_REG (reg_raw_mode[i], i));
+	web->id = last_num_webs++;
+	hardreg2web[web->regno] = web;
+      }
+  num_webs = last_num_webs;
+
+  /* Now create all artificial subwebs, i.e. those, which do
+     not correspond to a real subreg in the current function's RTL, but
+     which nevertheless is a target of a conflict.
+     XXX we need to merge this loop with the one above, which means, we need
+     a way to later override the artificiality.  Beware: currently
+     add_subweb_2() relies on the existence of normal subwebs for deducing
+     a sane mode to use for the artificial subwebs.  */
+  for (i = 0; i < df->def_id + df->use_id; i++)
+    {
+      struct web_part *wp = &web_parts[i];
+      struct tagged_conflict *cl;
+      struct web *web;
+      if (wp->uplink || !wp->ref)
+	{
+	  if (wp->sub_conflicts)
+	    abort ();
+	  continue;
+	}
+      web = def2web[i];
+      web = find_web_for_subweb (web);
+      for (cl = wp->sub_conflicts; cl; cl = cl->next)
+        if (!find_subweb_2 (web, cl->size_word))
+	  add_subweb_2 (web, cl->size_word);
+    }
+
+  /* And now create artificial subwebs needed for representing the inverse
+     of some subwebs.  This also gives IDs to all subwebs.  */
+  webnum = last_num_webs;
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      if (web->subreg_next)
+	{
+	  struct web *sweb;
+          build_inverse_webs (web);
+	  for (sweb = web->subreg_next; sweb; sweb = sweb->subreg_next)
+	    sweb->id = webnum++;
+	}
+    }
+
+  /* Now that everyone has an ID, we can setup the id2web array.  */
+  id2web = (struct web **) xcalloc (webnum, sizeof (id2web[0]));
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      ID2WEB (web->id) = web;
+      for (web = web->subreg_next; web; web = web->subreg_next)
+        ID2WEB (web->id) = web;
+    }
+  num_subwebs = webnum - last_num_webs;
+  num_allwebs = num_webs + num_subwebs;
+  num_webs += num_subwebs;
+
+  /* Allocate and clear the conflict graph bitmaps.  */
+  igraph = sbitmap_alloc (num_webs * num_webs / 2);
+  sup_igraph = sbitmap_alloc (num_webs * num_webs);
+  sbitmap_zero (igraph);
+  sbitmap_zero (sup_igraph);
+
+  /* Distibute the references to their webs.  */
+  init_webs_defs_uses ();
+  /* And do some sanity checks if old webs, and those recreated from the
+     really are the same.  */
+  compare_and_free_webs (&copy_webs);
+  free (all_refs);
+}
+
+/* This deletes all conflicts to and from webs which need to be renewed
+   in this pass of the allocator, i.e. those which were spilled in the
+   last pass.  Furthermore it also rebuilds the bitmaps for the remaining
+   conflicts.  */
+
+static void
+reset_conflicts ()
+{
+  unsigned int i;
+  bitmap newwebs = BITMAP_XMALLOC ();
+  for (i = 0; i < num_webs - num_subwebs; i++)
+    {
+      struct web *web = ID2WEB (i);
+      /* Hardreg webs and non-old webs are new webs (which
+	 need rebuilding).  */
+      if (web->type == PRECOLORED || !web->old_web)
+	bitmap_set_bit (newwebs, web->id);
+    }
+
+  for (i = 0; i < num_webs - num_subwebs; i++)
+    {
+      struct web *web = ID2WEB (i);
+      struct conflict_link *cl;
+      struct conflict_link **pcl;
+      pcl = &(web->conflict_list);
+
+      /* First restore the conflict list to be like it was before
+	 coalescing.  */
+      if (web->have_orig_conflicts)
+	{
+	  web->conflict_list = web->orig_conflict_list;
+	  web->orig_conflict_list = NULL;
+	}
+      if (web->orig_conflict_list)
+	abort ();
+
+      /* New non-precolored webs, have no conflict list.  */
+      if (web->type != PRECOLORED && !web->old_web)
+	{
+	  *pcl = NULL;
+	  /* Useless conflicts will be rebuilt completely.  But check
+	     for cleanlyness, as the web might have come from the
+	     free list.  */
+	  if (bitmap_first_set_bit (web->useless_conflicts) >= 0)
+	    abort ();
+	}
+      else
+	{
+	  /* Useless conflicts with new webs will be rebuilt if they
+	     are still there.  */
+	  bitmap_operation (web->useless_conflicts, web->useless_conflicts,
+			    newwebs, BITMAP_AND_COMPL);
+	  /* Go through all conflicts, and retain those to old webs.  */
+	  for (cl = web->conflict_list; cl; cl = cl->next)
+	    {
+	      if (cl->t->old_web || cl->t->type == PRECOLORED)
+		{
+		  *pcl = cl;
+		  pcl = &(cl->next);
+
+		  /* Also restore the entries in the igraph bitmaps.  */
+		  web->num_conflicts += 1 + cl->t->add_hardregs;
+		  SET_BIT (sup_igraph, (web->id * num_webs + cl->t->id));
+		  /* No subconflicts mean full webs conflict.  */
+		  if (!cl->sub)
+		    SET_BIT (igraph, igraph_index (web->id, cl->t->id));
+		  else
+		    /* Else only the parts in cl->sub must be in the
+		       bitmap.  */
+		    {
+		      struct sub_conflict *sl;
+		      for (sl = cl->sub; sl; sl = sl->next)
+			SET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
+		    }
+		}
+	    }
+	  *pcl = NULL;
+	}
+      web->have_orig_conflicts = 0;
+    }
+  BITMAP_XFREE (newwebs);
+}
+
+/* For each web check it's num_conflicts member against that
+   number, as calculated from scratch from all neighbors.  */
+
+static void
+check_conflict_numbers ()
+{
+  unsigned int i;
+  for (i = 0; i < num_webs; i++)
+    {
+      struct web *web = ID2WEB (i);
+      int new_conf = 0 * web->add_hardregs;
+      struct conflict_link *cl;
+      for (cl = web->conflict_list; cl; cl = cl->next)
+	if (cl->t->type != SELECT && cl->t->type != COALESCED)
+	  new_conf += 1 + cl->t->add_hardregs;
+      if (web->type != PRECOLORED && new_conf != web->num_conflicts)
+	abort ();
+    }
+}
+
+/* Convert the conflicts between web parts to conflicts between full webs.
+
+   This can't be done in parts_to_webs(), because for recording conflicts
+   between webs we need to know their final usable_regs set, which is used
+   to discard non-conflicts (between webs having no hard reg in common).
+   But this is set for spill temporaries only after the webs itself are
+   built.  Until then the usable_regs set is based on the pseudo regno used
+   in this web, which may contain far less registers than later determined.
+   This would result in us loosing conflicts (due to record_conflict()
+   thinking that a web can only be allocated to the current usable_regs,
+   whereas later this is extended) leading to colorings, where some regs which
+   in reality conflict get the same color.  */
+
+static void
+conflicts_between_webs (df)
+     struct df *df;
+{
+  unsigned int i;
+  struct dlist *d;
+  bitmap ignore_defs = BITMAP_XMALLOC ();
+  unsigned int have_ignored;
+  unsigned int *pass_cache = (unsigned int *) xcalloc (num_webs, sizeof (int));
+  unsigned int pass = 0;
+
+  if (ra_pass > 1)
+    reset_conflicts ();
+
+  /* It is possible, that in the conflict bitmaps still some defs I are noted,
+     which have web_parts[I].ref being NULL.  This can happen, when from the
+     last iteration the conflict bitmap for this part wasn't deleted, but a
+     conflicting move insn was removed.  It's DEF is still in the conflict
+     bitmap, but it doesn't exist anymore in df->defs.  To not have to check
+     it in the tight loop below, we instead remember the ID's of them in a
+     bitmap, and loop only over IDs which are not in it.  */
+  for (i = 0; i < df->def_id; i++)
+    if (web_parts[i].ref == NULL)
+      bitmap_set_bit (ignore_defs, i);
+  have_ignored = (bitmap_first_set_bit (ignore_defs) >= 0);
+
+  /* Now record all conflicts between webs.  Note that we only check
+     the conflict bitmaps of all defs.  Conflict bitmaps are only in
+     webpart roots.  If they are in uses, those uses are roots, which
+     means, that this is an uninitialized web, whose conflicts
+     don't matter.  Nevertheless for hardregs we also need to check uses.
+     E.g. hardregs used for argument passing have no DEF in the RTL,
+     but if they have uses, they indeed conflict with all DEFs they
+     overlap.  */
+  for (i = 0; i < df->def_id + df->use_id; i++)
+    {
+      struct tagged_conflict *cl = web_parts[i].sub_conflicts;
+      struct web *supweb1;
+      if (!cl
+	  || (i >= df->def_id
+	      && DF_REF_REGNO (web_parts[i].ref) >= FIRST_PSEUDO_REGISTER))
+	continue;
+      supweb1 = def2web[i];
+      supweb1 = find_web_for_subweb (supweb1);
+      for (; cl; cl = cl->next)
+        if (cl->conflicts)
+	  {
+	    int j;
+	    struct web *web1 = find_subweb_2 (supweb1, cl->size_word);
+	    if (have_ignored)
+	      bitmap_operation (cl->conflicts, cl->conflicts, ignore_defs,
+			        BITMAP_AND_COMPL);
+	    /* We reduce the number of calls to record_conflict() with this
+	       pass thing.  record_conflict() itself also has some early-out
+	       optimizations, but here we can use the special properties of
+	       the loop (constant web1) to reduce that even more.
+	       We once used an sbitmap of already handled web indices,
+	       but sbitmaps are slow to clear and bitmaps are slow to
+	       set/test.  The current approach needs more memory, but
+	       locality is large.  */
+	    pass++;
+
+	    /* Note, that there are only defs in the conflicts bitset.  */
+	    EXECUTE_IF_SET_IN_BITMAP (
+	      cl->conflicts, 0, j,
+	      {
+		struct web *web2 = def2web[j];
+		unsigned int id2 = web2->id;
+		if (pass_cache[id2] != pass)
+		  {
+		    pass_cache[id2] = pass;
+		    record_conflict (web1, web2);
+		  }
+	      });
+	  }
+    }
+
+  free (pass_cache);
+  BITMAP_XFREE (ignore_defs);
+
+#ifdef STACK_REGS
+  /* Pseudos can't go in stack regs if they are live at the beginning of
+     a block that is reached by an abnormal edge.  */
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      int j;
+      if (web->live_over_abnormal)
+	for (j = FIRST_STACK_REG; j <= LAST_STACK_REG; j++)
+	  record_conflict (web, hardreg2web[j]);
+    }
+#endif
+}
+
+/* Remember that a web was spilled, and change some characteristics
+   accordingly.  */
+
+static void
+remember_web_was_spilled (web)
+     struct web *web;
+{
+  int i;
+  unsigned int found_size = 0;
+  int adjust;
+  web->spill_temp = 1;
+
+  /* From now on don't use reg_pref/alt_class (regno) anymore for
+     this web, but instead  usable_regs.  We can't use spill_temp for
+     this, as it might get reset later, when we are coalesced to a
+     non-spill-temp.  In that case we still want to use usable_regs.  */
+  web->use_my_regs = 1;
+
+  /* We don't constrain spill temporaries in any way for now.
+     It's wrong sometimes to have the same constraints or
+     preferences as the original pseudo, esp. if they were very narrow.
+     (E.g. there once was a reg wanting class AREG (only one register)
+     without alternative class.  As long, as also the spill-temps for
+     this pseudo had the same constraints it was spilled over and over.
+     Ideally we want some constraints also on spill-temps: Because they are
+     not only loaded/stored, but also worked with, any constraints from insn
+     alternatives needs applying.  Currently this is dealt with by reload, as
+     many other things, but at some time we want to integrate that
+     functionality into the allocator.  */
+  if (web->regno >= max_normal_pseudo)
+    {
+      COPY_HARD_REG_SET (web->usable_regs,
+			reg_class_contents[reg_preferred_class (web->regno)]);
+      IOR_HARD_REG_SET (web->usable_regs,
+			reg_class_contents[reg_alternate_class (web->regno)]);
+    }
+  else
+    COPY_HARD_REG_SET (web->usable_regs, reg_class_contents[(int) ALL_REGS]);
+  AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
+  prune_hardregs_for_mode (&web->usable_regs, PSEUDO_REGNO_MODE (web->regno));
+#ifdef CLASS_CANNOT_CHANGE_MODE
+  if (web->mode_changed)
+    AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
+			      (int) CLASS_CANNOT_CHANGE_MODE]);
+#endif
+  web->num_freedom = hard_regs_count (web->usable_regs);
+  if (!web->num_freedom)
+    abort();
+  COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
+  /* Now look for a class, which is subset of our constraints, to
+     setup add_hardregs, and regclass for debug output.  */
+  web->regclass = NO_REGS;
+  for (i = (int) ALL_REGS - 1; i > 0; i--)
+    {
+      unsigned int size;
+      HARD_REG_SET test;
+      COPY_HARD_REG_SET (test, reg_class_contents[i]);
+      AND_COMPL_HARD_REG_SET (test, never_use_colors);
+      GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found);
+      continue;
+    found:
+      /* Measure the actual number of bits which really are overlapping
+	 the target regset, not just the reg_class_size.  */
+      size = hard_regs_count (test);
+      if (found_size < size)
+	{
+          web->regclass = (enum reg_class) i;
+	  found_size = size;
+	}
+    }
+
+  adjust = 0 * web->add_hardregs;
+  web->add_hardregs =
+    CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
+  web->num_freedom -= web->add_hardregs;
+  if (!web->num_freedom)
+    abort();
+  adjust -= 0 * web->add_hardregs;
+  web->num_conflicts -= adjust;
+}
+
+/* Look at each web, if it is used as spill web.  Or better said,
+   if it will be spillable in this pass.  */
+
+static void
+detect_spill_temps ()
+{
+  struct dlist *d;
+  bitmap already = BITMAP_XMALLOC ();
+
+  /* Detect webs used for spill temporaries.  */
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+
+      /* Below only the detection of spill temporaries.  We never spill
+         precolored webs, so those can't be spill temporaries.  The code above
+         (remember_web_was_spilled) can't currently cope with hardregs
+         anyway.  */
+      if (web->regno < FIRST_PSEUDO_REGISTER)
+	continue;
+      /* Uninitialized webs can't be spill-temporaries.  */
+      if (web->num_defs == 0)
+	continue;
+
+      /* A web with only defs and no uses can't be spilled.  Nevertheless
+	 it must get a color, as it takes away an register from all webs
+	 live at these defs.  So we make it a short web.  */
+      if (web->num_uses == 0)
+	web->spill_temp = 3;
+      /* A web which was spilled last time, but for which no insns were
+         emitted (can happen with IR spilling ignoring sometimes
+	 all deaths).  */
+      else if (web->changed)
+	web->spill_temp = 1;
+      /* A spill temporary has one def, one or more uses, all uses
+	 are in one insn, and either the def or use insn was inserted
+	 by the allocator.  */
+      /* XXX not correct currently.  There might also be spill temps
+	 involving more than one def.  Usually that's an additional
+	 clobber in the using instruction.  We might also constrain
+	 ourself to that, instead of like currently marking all
+	 webs involving any spill insns at all.  */
+      else
+	{
+	  unsigned int i;
+	  int spill_involved = 0;
+	  for (i = 0; i < web->num_uses && !spill_involved; i++)
+	    if (DF_REF_INSN_UID (web->uses[i]) >= orig_max_uid)
+	      spill_involved = 1;
+	  for (i = 0; i < web->num_defs && !spill_involved; i++)
+	    if (DF_REF_INSN_UID (web->defs[i]) >= orig_max_uid)
+	      spill_involved = 1;
+
+	  if (spill_involved/* && ra_pass > 2*/)
+	    {
+	      int num_deaths = web->span_deaths;
+	      /* Mark webs involving at least one spill insn as
+		 spill temps.  */
+	      remember_web_was_spilled (web);
+	      /* Search for insns which define and use the web in question
+		 at the same time, i.e. look for rmw insns.  If these insns
+		 are also deaths of other webs they might have been counted
+		 as such into web->span_deaths.  But because of the rmw nature
+		 of this insn it is no point where a load/reload could be
+		 placed successfully (it would still conflict with the
+		 dead web), so reduce the number of spanned deaths by those
+		 insns.  Note that sometimes such deaths are _not_ counted,
+	         so negative values can result.  */
+	      bitmap_zero (already);
+	      for (i = 0; i < web->num_defs; i++)
+		{
+		  rtx insn = web->defs[i]->insn;
+		  if (TEST_BIT (insns_with_deaths, INSN_UID (insn))
+		      && !bitmap_bit_p (already, INSN_UID (insn)))
+		    {
+		      unsigned int j;
+		      bitmap_set_bit (already, INSN_UID (insn));
+		      /* Only decrement it once for each insn.  */
+		      for (j = 0; j < web->num_uses; j++)
+			if (web->uses[j]->insn == insn)
+			  {
+			    num_deaths--;
+			    break;
+			  }
+		    }
+		}
+	      /* But mark them specially if they could possibly be spilled,
+		 either because they cross some deaths (without the above
+		 mentioned ones) or calls.  */
+	      if (web->crosses_call || num_deaths > 0)
+		web->spill_temp = 1 * 2;
+	    }
+	  /* A web spanning no deaths can't be spilled either.  No loads
+	     would be created for it, ergo no defs.  So the insns wouldn't
+	     change making the graph not easier to color.  Make this also
+	     a short web.  Don't do this if it crosses calls, as these are
+	     also points of reloads.  */
+	  else if (web->span_deaths == 0 && !web->crosses_call)
+	    web->spill_temp = 3;
+	}
+      web->orig_spill_temp = web->spill_temp;
+    }
+  BITMAP_XFREE (already);
+}
+
+/* Returns nonzero if the rtx MEM refers somehow to a stack location.  */
+
+int
+memref_is_stack_slot (mem)
+     rtx mem;
+{
+  rtx ad = XEXP (mem, 0);
+  rtx x;
+  if (GET_CODE (ad) != PLUS || GET_CODE (XEXP (ad, 1)) != CONST_INT)
+    return 0;
+  x = XEXP (ad, 0);
+  if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+      || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
+      || x == stack_pointer_rtx)
+    return 1;
+  return 0;
+}
+
+/* Returns nonzero, if rtx X somewhere contains any pseudo register.  */
+
+static int
+contains_pseudo (x)
+     rtx x;
+{
+  const char *fmt;
+  int i;
+  if (GET_CODE (x) == SUBREG)
+    x = SUBREG_REG (x);
+  if (GET_CODE (x) == REG)
+    {
+      if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+        return 1;
+      else
+	return 0;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (x));
+  for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      {
+	if (contains_pseudo (XEXP (x, i)))
+	  return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+	int j;
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  if (contains_pseudo (XVECEXP (x, i, j)))
+	    return 1;
+      }
+  return 0;
+}
+
+/* Returns nonzero, if we are able to rematerialize something with
+   value X.  If it's not a general operand, we test if we can produce
+   a valid insn which set a pseudo to that value, and that insn doesn't
+   clobber anything.  */
+
+static GTY(()) rtx remat_test_insn;
+static int
+want_to_remat (x)
+     rtx x;
+{
+  int num_clobbers = 0;
+  int icode;
+
+  /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
+  if (general_operand (x, GET_MODE (x)))
+    return 1;
+
+  /* Otherwise, check if we can make a valid insn from it.  First initialize
+     our test insn if we haven't already.  */
+  if (remat_test_insn == 0)
+    {
+      remat_test_insn
+	= make_insn_raw (gen_rtx_SET (VOIDmode,
+				      gen_rtx_REG (word_mode,
+						   FIRST_PSEUDO_REGISTER * 2),
+				      const0_rtx));
+      NEXT_INSN (remat_test_insn) = PREV_INSN (remat_test_insn) = 0;
+    }
+
+  /* Now make an insn like the one we would make when rematerializing
+     the value X and see if valid.  */
+  PUT_MODE (SET_DEST (PATTERN (remat_test_insn)), GET_MODE (x));
+  SET_SRC (PATTERN (remat_test_insn)) = x;
+  /* XXX For now we don't allow any clobbers to be added, not just no
+     hardreg clobbers.  */
+  return ((icode = recog (PATTERN (remat_test_insn), remat_test_insn,
+			  &num_clobbers)) >= 0
+	  && (num_clobbers == 0
+	      /*|| ! added_clobbers_hard_reg_p (icode)*/));
+}
+
+/* Look at all webs, if they perhaps are rematerializable.
+   They are, if all their defs are simple sets to the same value,
+   and that value is simple enough, and want_to_remat() holds for it.  */
+
+static void
+detect_remat_webs ()
+{
+  struct dlist *d;
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      unsigned int i;
+      rtx pat = NULL_RTX;
+      /* Hardregs and useless webs aren't spilled -> no remat necessary.
+	 Defless webs obviously also can't be rematerialized.  */
+      if (web->regno < FIRST_PSEUDO_REGISTER || !web->num_defs
+	  || !web->num_uses)
+	continue;
+      for (i = 0; i < web->num_defs; i++)
+	{
+	  rtx insn;
+	  rtx set = single_set (insn = DF_REF_INSN (web->defs[i]));
+	  rtx src;
+	  if (!set)
+	    break;
+	  src = SET_SRC (set);
+	  /* When only subregs of the web are set it isn't easily
+	     rematerializable.  */
+	  if (!rtx_equal_p (SET_DEST (set), web->orig_x))
+	    break;
+	  /* If we already have a pattern it must be equal to the current.  */
+	  if (pat && !rtx_equal_p (pat, src))
+	    break;
+	  /* Don't do the expensive checks multiple times.  */
+	  if (pat)
+	    continue;
+	  /* For now we allow only constant sources.  */
+	  if ((CONSTANT_P (src)
+	       /* If the whole thing is stable already, it is a source for
+		  remat, no matter how complicated (probably all needed
+		  resources for it are live everywhere, and don't take
+		  additional register resources).  */
+	       /* XXX Currently we can't use patterns which contain
+		  pseudos, _even_ if they are stable.  The code simply isn't
+		  prepared for that.  All those operands can't be spilled (or
+		  the dependent remat webs are not remat anymore), so they
+		  would be oldwebs in the next iteration.  But currently
+		  oldwebs can't have their references changed.  The
+		  incremental machinery barfs on that.  */
+	       || (!rtx_unstable_p (src) && !contains_pseudo (src))
+	       /* Additionally also memrefs to stack-slots are usefull, when
+		  we created them ourself.  They might not have set their
+		  unchanging flag set, but nevertheless they are stable across
+		  the livetime in question.  */
+	       || (GET_CODE (src) == MEM
+		   && INSN_UID (insn) >= orig_max_uid
+		   && memref_is_stack_slot (src)))
+	      /* And we must be able to construct an insn without
+		 side-effects to actually load that value into a reg.  */
+	      && want_to_remat (src))
+	    pat = src;
+	  else
+	    break;
+	}
+      if (pat && i == web->num_defs)
+	web->pattern = pat;
+    }
+}
+
+/* Determine the spill costs of all webs.  */
+
+static void
+determine_web_costs ()
+{
+  struct dlist *d;
+  for (d = WEBS(INITIAL); d; d = d->next)
+    {
+      unsigned int i, num_loads;
+      int load_cost, store_cost;
+      unsigned HOST_WIDE_INT w;
+      struct web *web = DLIST_WEB (d);
+      if (web->type == PRECOLORED)
+	continue;
+      /* Get costs for one load/store.  Note that we offset them by 1,
+	 because some patterns have a zero rtx_cost(), but we of course
+	 still need the actual load/store insns.  With zero all those
+	 webs would be the same, no matter how often and where
+	 they are used.  */
+      if (web->pattern)
+	{
+	  /* This web is rematerializable.  Beware, we set store_cost to
+	     zero optimistically assuming, that we indeed don't emit any
+	     stores in the spill-code addition.  This might be wrong if
+	     at the point of the load not all needed resources are
+	     available, in which case we emit a stack-based load, for
+	     which we in turn need the according stores.  */
+	  load_cost = 1 + rtx_cost (web->pattern, 0);
+	  store_cost = 0;
+	}
+      else
+	{
+	  load_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
+					    web->regclass, 1);
+	  store_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x),
+					     web->regclass, 0);
+	}
+      /* We create only loads at deaths, whose number is in span_deaths.  */
+      num_loads = MIN (web->span_deaths, web->num_uses);
+      for (w = 0, i = 0; i < web->num_uses; i++)
+	w += DF_REF_BB (web->uses[i])->frequency + 1;
+      if (num_loads < web->num_uses)
+	w = (w * num_loads + web->num_uses - 1) / web->num_uses;
+      web->spill_cost = w * load_cost;
+      if (store_cost)
+	{
+	  for (w = 0, i = 0; i < web->num_defs; i++)
+	    w += DF_REF_BB (web->defs[i])->frequency + 1;
+	  web->spill_cost += w * store_cost;
+	}
+      web->orig_spill_cost = web->spill_cost;
+    }
+}
+
+/* Detect webs which are set in a conditional jump insn (possibly a
+   decrement-and-branch type of insn), and mark them not to be
+   spillable.  The stores for them would need to be placed on edges,
+   which destroys the CFG.  (Somewhen we want to deal with that XXX)  */
+
+static void
+detect_webs_set_in_cond_jump ()
+{
+  basic_block bb;
+  FOR_EACH_BB (bb)
+    if (GET_CODE (bb->end) == JUMP_INSN)
+      {
+	struct df_link *link;
+	for (link = DF_INSN_DEFS (df, bb->end); link; link = link->next)
+	  if (link->ref && DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER)
+	    {
+	      struct web *web = def2web[DF_REF_ID (link->ref)];
+	      web->orig_spill_temp = web->spill_temp = 3;
+	    }
+      }
+}
+
+/* Second top-level function of this file.
+   Converts the connected web parts to full webs.  This means, it allocates
+   all webs, and initializes all fields, including detecting spill
+   temporaries.  It does not distribute moves to their corresponding webs,
+   though.  */
+
+static void
+make_webs (df)
+     struct df *df;
+{
+  /* First build all the webs itself.  They are not related with
+     others yet.  */
+  parts_to_webs (df);
+  /* Now detect spill temporaries to initialize their usable_regs set.  */
+  detect_spill_temps ();
+  detect_webs_set_in_cond_jump ();
+  /* And finally relate them to each other, meaning to record all possible
+     conflicts between webs (see the comment there).  */
+  conflicts_between_webs (df);
+  detect_remat_webs ();
+  determine_web_costs ();
+}
+
+/* Distribute moves to the corresponding webs.  */
+
+static void
+moves_to_webs (df)
+     struct df *df;
+{
+  struct df_link *link;
+  struct move_list *ml;
+
+  /* Distribute all moves to their corresponding webs, making sure,
+     each move is in a web maximally one time (happens on some strange
+     insns).  */
+  for (ml = wl_moves; ml; ml = ml->next)
+    {
+      struct move *m = ml->move;
+      struct web *web;
+      struct move_list *newml;
+      if (!m)
+	continue;
+      m->type = WORKLIST;
+      m->dlink = NULL;
+      /* Multiple defs/uses can happen in moves involving hard-regs in
+	 a wider mode.  For those df.* creates use/def references for each
+	 real hard-reg involved.  For coalescing we are interested in
+	 the smallest numbered hard-reg.  */
+      for (link = DF_INSN_DEFS (df, m->insn); link; link = link->next)
+        if (link->ref)
+	  {
+	    web = def2web[DF_REF_ID (link->ref)];
+	    web = find_web_for_subweb (web);
+	    if (!m->target_web || web->regno < m->target_web->regno)
+	      m->target_web = web;
+	  }
+      for (link = DF_INSN_USES (df, m->insn); link; link = link->next)
+        if (link->ref)
+	  {
+	    web = use2web[DF_REF_ID (link->ref)];
+	    web = find_web_for_subweb (web);
+	    if (!m->source_web || web->regno < m->source_web->regno)
+	      m->source_web = web;
+	  }
+      if (m->source_web && m->target_web
+	  /* If the usable_regs don't intersect we can't coalesce the two
+	     webs anyway, as this is no simple copy insn (it might even
+	     need an intermediate stack temp to execute this "copy" insn). */
+	  && hard_regs_intersect_p (&m->source_web->usable_regs,
+				    &m->target_web->usable_regs))
+	{
+	  if (!flag_ra_optimistic_coalescing)
+	    {
+	      struct move_list *test = m->source_web->moves;
+	      for (; test && test->move != m; test = test->next);
+	      if (! test)
+		{
+		  newml = (struct move_list*)
+		    ra_alloc (sizeof (struct move_list));
+		  newml->move = m;
+		  newml->next = m->source_web->moves;
+		  m->source_web->moves = newml;
+		}
+	      test = m->target_web->moves;
+	      for (; test && test->move != m; test = test->next);
+	      if (! test)
+		{
+		  newml = (struct move_list*)
+		    ra_alloc (sizeof (struct move_list));
+		  newml->move = m;
+		  newml->next = m->target_web->moves;
+		  m->target_web->moves = newml;
+		}
+	    }
+	}
+      else
+	/* Delete this move.  */
+	ml->move = NULL;
+    }
+}
+
+/* Handle tricky asm insns.
+   Supposed to create conflicts to hardregs which aren't allowed in
+   the constraints.  Doesn't actually do that, as it might confuse
+   and constrain the allocator too much.  */
+
+static void
+handle_asm_insn (df, insn)
+     struct df *df;
+     rtx insn;
+{
+  const char *constraints[MAX_RECOG_OPERANDS];
+  enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
+  int i, noperands, in_output;
+  HARD_REG_SET clobbered, allowed, conflict;
+  rtx pat;
+  if (! INSN_P (insn)
+      || (noperands = asm_noperands (PATTERN (insn))) < 0)
+    return;
+  pat = PATTERN (insn);
+  CLEAR_HARD_REG_SET (clobbered);
+
+  if (GET_CODE (pat) == PARALLEL)
+    for (i = 0; i < XVECLEN (pat, 0); i++)
+      {
+	rtx t = XVECEXP (pat, 0, i);
+	if (GET_CODE (t) == CLOBBER && GET_CODE (XEXP (t, 0)) == REG
+	    && REGNO (XEXP (t, 0)) < FIRST_PSEUDO_REGISTER)
+	  SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0)));
+      }
+
+  decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc,
+		       constraints, operand_mode);
+  in_output = 1;
+  for (i = 0; i < noperands; i++)
+    {
+      const char *p = constraints[i];
+      int cls = (int) NO_REGS;
+      struct df_link *link;
+      rtx reg;
+      struct web *web;
+      int nothing_allowed = 1;
+      reg = recog_data.operand[i];
+
+      /* Look, if the constraints apply to a pseudo reg, and not to
+	 e.g. a mem.  */
+      while (GET_CODE (reg) == SUBREG
+	     || GET_CODE (reg) == ZERO_EXTRACT
+	     || GET_CODE (reg) == SIGN_EXTRACT
+	     || GET_CODE (reg) == STRICT_LOW_PART)
+	reg = XEXP (reg, 0);
+      if (GET_CODE (reg) != REG || REGNO (reg) < FIRST_PSEUDO_REGISTER)
+	continue;
+
+      /* Search the web corresponding to this operand.  We depend on
+	 that decode_asm_operands() places the output operands
+	 before the input operands.  */
+      while (1)
+	{
+	  if (in_output)
+	    link = df->insns[INSN_UID (insn)].defs;
+	  else
+	    link = df->insns[INSN_UID (insn)].uses;
+	  while (link && link->ref && DF_REF_REAL_REG (link->ref) != reg)
+	    link = link->next;
+	  if (!link || !link->ref)
+	    {
+	      if (in_output)
+	        in_output = 0;
+	      else
+	        abort ();
+	    }
+	  else
+	    break;
+	}
+      if (in_output)
+	web = def2web[DF_REF_ID (link->ref)];
+      else
+	web = use2web[DF_REF_ID (link->ref)];
+      reg = DF_REF_REG (link->ref);
+
+      /* Find the constraints, noting the allowed hardregs in allowed.  */
+      CLEAR_HARD_REG_SET (allowed);
+      while (1)
+	{
+	  char c = *p++;
+
+	  if (c == '\0' || c == ',' || c == '#')
+	    {
+	      /* End of one alternative - mark the regs in the current
+	       class, and reset the class.
+	       */
+	      IOR_HARD_REG_SET (allowed, reg_class_contents[cls]);
+	      if (cls != NO_REGS)
+		nothing_allowed = 0;
+	      cls = NO_REGS;
+	      if (c == '#')
+		do {
+		    c = *p++;
+		} while (c != '\0' && c != ',');
+	      if (c == '\0')
+	        break;
+	      continue;
+	    }
+
+	  switch (c)
+	    {
+	      case '=': case '+': case '*': case '%': case '?': case '!':
+	      case '0': case '1': case '2': case '3': case '4': case 'm':
+	      case '<': case '>': case 'V': case 'o': case '&': case 'E':
+	      case 'F': case 's': case 'i': case 'n': case 'X': case 'I':
+	      case 'J': case 'K': case 'L': case 'M': case 'N': case 'O':
+	      case 'P':
+		break;
+
+	      case 'p':
+		cls = (int) reg_class_subunion[cls][(int) BASE_REG_CLASS];
+		nothing_allowed = 0;
+	        break;
+
+	      case 'g':
+	      case 'r':
+		cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS];
+		nothing_allowed = 0;
+		break;
+
+	      default:
+		cls =
+		  (int) reg_class_subunion[cls][(int)
+						REG_CLASS_FROM_LETTER (c)];
+	    }
+	}
+
+      /* Now make conflicts between this web, and all hardregs, which
+	 are not allowed by the constraints.  */
+      if (nothing_allowed)
+	{
+	  /* If we had no real constraints nothing was explicitely
+	     allowed, so we allow the whole class (i.e. we make no
+	     additional conflicts).  */
+	  CLEAR_HARD_REG_SET (conflict);
+	}
+      else
+	{
+	  COPY_HARD_REG_SET (conflict, usable_regs
+			     [reg_preferred_class (web->regno)]);
+	  IOR_HARD_REG_SET (conflict, usable_regs
+			    [reg_alternate_class (web->regno)]);
+	  AND_COMPL_HARD_REG_SET (conflict, allowed);
+	  /* We can't yet establish these conflicts.  Reload must go first
+	     (or better said, we must implement some functionality of reload).
+	     E.g. if some operands must match, and they need the same color
+	     we don't see yet, that they do not conflict (because they match).
+	     For us it looks like two normal references with different DEFs,
+	     so they conflict, and as they both need the same color, the
+	     graph becomes uncolorable.  */
+#if 0
+	  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
+	    if (TEST_HARD_REG_BIT (conflict, c))
+	      record_conflict (web, hardreg2web[c]);
+#endif
+	}
+      if (rtl_dump_file)
+	{
+	  int c;
+	  ra_debug_msg (DUMP_ASM, " ASM constrain Web %d conflicts with:", web->id);
+	  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
+	    if (TEST_HARD_REG_BIT (conflict, c))
+	      ra_debug_msg (DUMP_ASM, " %d", c);
+	  ra_debug_msg (DUMP_ASM, "\n");
+	}
+    }
+}
+
+/* The real toplevel function in this file.
+   Build (or rebuilds) the complete interference graph with webs
+   and conflicts.  */
+
+void
+build_i_graph (df)
+     struct df *df;
+{
+  rtx insn;
+
+  init_web_parts (df);
+
+  sbitmap_zero (move_handled);
+  wl_moves = NULL;
+
+  build_web_parts_and_conflicts (df);
+
+  /* For read-modify-write instructions we may have created two webs.
+     Reconnect them here.  (s.a.)  */
+  connect_rmw_web_parts (df);
+
+  /* The webs are conceptually complete now, but still scattered around as
+     connected web parts.  Collect all information and build the webs
+     including all conflicts between webs (instead web parts).  */
+  make_webs (df);
+  moves_to_webs (df);
+
+  /* Look for additional constraints given by asms.  */
+  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    handle_asm_insn (df, insn);
+}
+
+/* Allocates or reallocates most memory for the interference graph and
+   assiciated structures.  If it reallocates memory (meaning, this is not
+   the first pass), this also changes some structures to reflect the
+   additional entries in various array, and the higher number of
+   defs and uses.  */
+
+void
+ra_build_realloc (df)
+     struct df *df;
+{
+  struct web_part *last_web_parts = web_parts;
+  struct web **last_def2web = def2web;
+  struct web **last_use2web = use2web;
+  sbitmap last_live_over_abnormal = live_over_abnormal;
+  unsigned int i;
+  struct dlist *d;
+  move_handled = sbitmap_alloc (get_max_uid () );
+  web_parts = (struct web_part *) xcalloc (df->def_id + df->use_id,
+					   sizeof web_parts[0]);
+  def2web = (struct web **) xcalloc (df->def_id + df->use_id,
+				     sizeof def2web[0]);
+  use2web = &def2web[df->def_id];
+  live_over_abnormal = sbitmap_alloc (df->use_id);
+  sbitmap_zero (live_over_abnormal);
+
+  /* First go through all old defs and uses.  */
+  for (i = 0; i < last_def_id + last_use_id; i++)
+    {
+      /* And relocate them to the new array.  This is made ugly by the
+         fact, that defs and uses are placed consecutive into one array.  */
+      struct web_part *dest = &web_parts[i < last_def_id
+					 ? i : (df->def_id + i - last_def_id)];
+      struct web_part *up;
+      *dest = last_web_parts[i];
+      up = dest->uplink;
+      dest->uplink = NULL;
+
+      /* Also relocate the uplink to point into the new array.  */
+      if (up && up->ref)
+	{
+	  unsigned int id = DF_REF_ID (up->ref);
+	  if (up < &last_web_parts[last_def_id])
+	    {
+	      if (df->defs[id])
+	        dest->uplink = &web_parts[DF_REF_ID (up->ref)];
+	    }
+	  else if (df->uses[id])
+	    dest->uplink = &web_parts[df->def_id + DF_REF_ID (up->ref)];
+	}
+    }
+
+  /* Also set up the def2web and use2web arrays, from the last pass.i
+     Remember also the state of live_over_abnormal.  */
+  for (i = 0; i < last_def_id; i++)
+    {
+      struct web *web = last_def2web[i];
+      if (web)
+	{
+	  web = find_web_for_subweb (web);
+	  if (web->type != FREE && web->type != PRECOLORED)
+	    def2web[i] = last_def2web[i];
+	}
+    }
+  for (i = 0; i < last_use_id; i++)
+    {
+      struct web *web = last_use2web[i];
+      if (web)
+	{
+	  web = find_web_for_subweb (web);
+	  if (web->type != FREE && web->type != PRECOLORED)
+	    use2web[i] = last_use2web[i];
+	}
+      if (TEST_BIT (last_live_over_abnormal, i))
+	SET_BIT (live_over_abnormal, i);
+    }
+
+  /* We don't have any subwebs for now.  Somewhen we might want to
+     remember them too, instead of recreating all of them every time.
+     The problem is, that which subwebs we need, depends also on what
+     other webs and subwebs exist, and which conflicts are there.
+     OTOH it should be no problem, if we had some more subwebs than strictly
+     needed.  Later.  */
+  for (d = WEBS(FREE); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      struct web *wnext;
+      for (web = web->subreg_next; web; web = wnext)
+	{
+	  wnext = web->subreg_next;
+	  free (web);
+	}
+      DLIST_WEB (d)->subreg_next = NULL;
+    }
+
+  /* The uses we anyway are going to check, are not yet live over an abnormal
+     edge.  In fact, they might actually not anymore, due to added
+     loads.  */
+  if (last_check_uses)
+    sbitmap_difference (live_over_abnormal, live_over_abnormal,
+		        last_check_uses);
+
+  if (last_def_id || last_use_id)
+    {
+      sbitmap_free (last_live_over_abnormal);
+      free (last_web_parts);
+      free (last_def2web);
+    }
+  if (!last_max_uid)
+    {
+      /* Setup copy cache, for copy_insn_p ().  */
+      copy_cache = (struct copy_p_cache *)
+	xcalloc (get_max_uid (), sizeof (copy_cache[0]));
+      init_bb_info ();
+    }
+  else
+    {
+      copy_cache = (struct copy_p_cache *)
+	xrealloc (copy_cache, get_max_uid () * sizeof (copy_cache[0]));
+      memset (&copy_cache[last_max_uid], 0,
+	      (get_max_uid () - last_max_uid) * sizeof (copy_cache[0]));
+    }
+}
+
+/* Free up/clear some memory, only needed for one pass.  */
+
+void
+ra_build_free ()
+{
+  struct dlist *d;
+  unsigned int i;
+
+  /* Clear the moves associated with a web (we also need to look into
+     subwebs here).  */
+  for (i = 0; i < num_webs; i++)
+    {
+      struct web *web = ID2WEB (i);
+      if (!web)
+	abort ();
+      if (i >= num_webs - num_subwebs
+	  && (web->conflict_list || web->orig_conflict_list))
+	abort ();
+      web->moves = NULL;
+    }
+  /* All webs in the free list have no defs or uses anymore.  */
+  for (d = WEBS(FREE); d; d = d->next)
+    {
+      struct web *web = DLIST_WEB (d);
+      if (web->defs)
+	free (web->defs);
+      web->defs = NULL;
+      if (web->uses)
+	free (web->uses);
+      web->uses = NULL;
+      /* We can't free the subwebs here, as they are referenced from
+	 def2web[], and possibly needed in the next ra_build_realloc().
+	 We free them there (or in free_all_mem()).  */
+    }
+
+  /* Free all conflict bitmaps from web parts.  Note that we clear
+     _all_ these conflicts, and don't rebuild them next time for uses
+     which aren't rechecked.  This mean, that those conflict bitmaps
+     only contain the incremental information.  The cumulative one
+     is still contained in the edges of the I-graph, i.e. in
+     conflict_list (or orig_conflict_list) of the webs.  */
+  for (i = 0; i < df->def_id + df->use_id; i++)
+    {
+      struct tagged_conflict *cl;
+      for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next)
+	{
+	  if (cl->conflicts)
+	    BITMAP_XFREE (cl->conflicts);
+	}
+      web_parts[i].sub_conflicts = NULL;
+    }
+
+  wl_moves = NULL;
+
+  free (id2web);
+  free (move_handled);
+  sbitmap_free (sup_igraph);
+  sbitmap_free (igraph);
+}
+
+/* Free all memory for the interference graph structures.  */
+
+void
+ra_build_free_all (df)
+     struct df *df;
+{
+  unsigned int i;
+
+  free_bb_info ();
+  free (copy_cache);
+  copy_cache = NULL;
+  for (i = 0; i < df->def_id + df->use_id; i++)
+    {
+      struct tagged_conflict *cl;
+      for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next)
+	{
+	  if (cl->conflicts)
+	    BITMAP_XFREE (cl->conflicts);
+	}
+      web_parts[i].sub_conflicts = NULL;
+    }
+  sbitmap_free (live_over_abnormal);
+  free (web_parts);
+  web_parts = NULL;
+  if (last_check_uses)
+    sbitmap_free (last_check_uses);
+  last_check_uses = NULL;
+  free (def2web);
+  use2web = NULL;
+  def2web = NULL;
+}
+
+#include "gt-ra-build.h"
+
+/*
+vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
+*/