ra-colorize.c

/* Graph coloring register allocator
   Copyright (C) 2001, 2002, 2004 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 "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "function.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "df.h"
#include "output.h"
#include "ra.h"

/* This file is part of the graph coloring register allocator.
   It contains the graph colorizer.  Given an interference graph
   as set up in ra-build.c the toplevel function in this file
   (ra_colorize_graph) colorizes the graph, leaving a list
   of colored, coalesced and spilled nodes.

   The algorithm used is a merge of George & Appels iterative coalescing
   and optimistic coalescing, switchable at runtime.  The current default
   is "optimistic coalescing +", which is based on the normal Briggs/Cooper
   framework.  We can also use biased coloring.  Most of the structure
   here follows the different papers.

   Additionally there is a custom step to locally improve the overall
   spill cost of the colored graph (recolor_spills).  */

static void push_list (struct dlist *, struct dlist **);
static void push_list_end (struct dlist *, struct dlist **);
static void free_dlist (struct dlist **);
static void put_web_at_end (struct web *, enum ra_node_type);
static void put_move (struct move *, enum move_type);
static void build_worklists (struct df *);
static void enable_move (struct web *);
static void decrement_degree (struct web *, int);
static void simplify (void);
static void remove_move_1 (struct web *, struct move *);
static void remove_move (struct web *, struct move *);
static void add_worklist (struct web *);
static int ok (struct web *, struct web *);
static int conservative (struct web *, struct web *);
static inline unsigned int simplify_p (enum ra_node_type);
static void combine (struct web *, struct web *);
static void coalesce (void);
static void freeze_moves (struct web *);
static void freeze (void);
static void select_spill (void);
static int color_usable_p (int, HARD_REG_SET, HARD_REG_SET,
			   enum machine_mode);
int get_free_reg (HARD_REG_SET, HARD_REG_SET, enum machine_mode);
static int get_biased_reg (HARD_REG_SET, HARD_REG_SET, HARD_REG_SET,
			   HARD_REG_SET, enum machine_mode);
static int count_long_blocks (HARD_REG_SET, int);
static char * hardregset_to_string (HARD_REG_SET);
static void calculate_dont_begin (struct web *, HARD_REG_SET *);
static void colorize_one_web (struct web *, int);
static void assign_colors (void);
static void try_recolor_web (struct web *);
static void insert_coalesced_conflicts (void);
static int comp_webs_maxcost (const void *, const void *);
static void recolor_spills (void);
static void check_colors (void);
static void restore_conflicts_from_coalesce (struct web *);
static void break_coalesced_spills (void);
static void unalias_web (struct web *);
static void break_aliases_to_web (struct web *);
static void break_precolored_alias (struct web *);
static void init_web_pairs (void);
static void add_web_pair_cost (struct web *, struct web *,
		               unsigned HOST_WIDE_INT, unsigned int);
static int comp_web_pairs (const void *, const void *);
static void sort_and_combine_web_pairs (int);
static int ok_class (struct web *, struct web *);
static void aggressive_coalesce (void);
static void extended_coalesce_2 (void);
static void check_uncoalesced_moves (void);

static struct dlist *mv_worklist, *mv_coalesced, *mv_constrained;
static struct dlist *mv_frozen, *mv_active;

/* Push a node onto the front of the list.  */

static void
push_list (struct dlist *x, struct dlist **list)
{
  if (x->next || x->prev)
    abort ();
  x->next = *list;
  if (*list)
    (*list)->prev = x;
  *list = x;
}

static void
push_list_end (struct dlist *x, struct dlist **list)
{
  if (x->prev || x->next)
    abort ();
  if (!*list)
    {
      *list = x;
      return;
    }
  while ((*list)->next)
    list = &((*list)->next);
  x->prev = *list;
  (*list)->next = x;
}

/* Remove a node from the list.  */

void
remove_list (struct dlist *x, struct dlist **list)
{
  struct dlist *y = x->prev;
  if (y)
    y->next = x->next;
  else
    *list = x->next;
  y = x->next;
  if (y)
    y->prev = x->prev;
  x->next = x->prev = NULL;
}

/* Pop the front of the list.  */

struct dlist *
pop_list (struct dlist **list)
{
  struct dlist *r = *list;
  if (r)
    remove_list (r, list);
  return r;
}

/* Free the given double linked list.  */

static void
free_dlist (struct dlist **list)
{
  *list = NULL;
}

/* The web WEB should get the given new TYPE.  Put it onto the
   appropriate list.
   Inline, because it's called with constant TYPE every time.  */

inline void
put_web (struct web *web, enum ra_node_type type)
{
  switch (type)
    {
      case INITIAL:
      case FREE:
      case FREEZE:
      case SPILL:
      case SPILLED:
      case COALESCED:
      case COLORED:
      case SELECT:
	push_list (web->dlink, &WEBS(type));
	break;
      case PRECOLORED:
	push_list (web->dlink, &WEBS(INITIAL));
	break;
      case SIMPLIFY:
	if (web->spill_temp)
	  push_list (web->dlink, &WEBS(type = SIMPLIFY_SPILL));
	else if (web->add_hardregs)
	  push_list (web->dlink, &WEBS(type = SIMPLIFY_FAT));
	else
	  push_list (web->dlink, &WEBS(SIMPLIFY));
	break;
      default:
	abort ();
    }
  web->type = type;
}

/* After we are done with the whole pass of coloring/spilling,
   we reset the lists of webs, in preparation of the next pass.
   The spilled webs become free, colored webs go to the initial list,
   coalesced webs become free or initial, according to what type of web
   they are coalesced to.  */

void
reset_lists (void)
{
  struct dlist *d;
  unsigned int i;
  if (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_SPILL) || WEBS(SIMPLIFY_FAT)
      || WEBS(FREEZE) || WEBS(SPILL) || WEBS(SELECT))
    abort ();

  while ((d = pop_list (&WEBS(COALESCED))) != NULL)
    {
      struct web *web = DLIST_WEB (d);
      struct web *aweb = alias (web);
      /* Note, how alias() becomes invalid through the two put_web()'s
	 below.  It might set the type of a web to FREE (from COALESCED),
	 which itself is a target of aliasing (i.e. in the middle of
	 an alias chain).  We can handle this by checking also for
	 type == FREE.  Note nevertheless, that alias() is invalid
	 henceforth.  */
      if (aweb->type == SPILLED || aweb->type == FREE)
	put_web (web, FREE);
      else
	put_web (web, INITIAL);
    }
  while ((d = pop_list (&WEBS(SPILLED))) != NULL)
    put_web (DLIST_WEB (d), FREE);
  while ((d = pop_list (&WEBS(COLORED))) != NULL)
    put_web (DLIST_WEB (d), INITIAL);

  /* All free webs have no conflicts anymore.  */
  for (d = WEBS(FREE); d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      BITMAP_XFREE (web->useless_conflicts);
      web->useless_conflicts = NULL;
    }

  /* Sanity check, that we only have free, initial or precolored webs.  */
  for (i = 0; i < num_webs; i++)
    {
      struct web *web = ID2WEB (i);
      if (web->type != INITIAL && web->type != FREE && web->type != PRECOLORED)
	abort ();
    }
  free_dlist (&mv_worklist);
  free_dlist (&mv_coalesced);
  free_dlist (&mv_constrained);
  free_dlist (&mv_frozen);
  free_dlist (&mv_active);
}

/* Similar to put_web(), but add the web to the end of the appropriate
   list.  Additionally TYPE may not be SIMPLIFY.  */

static void
put_web_at_end (struct web *web, enum ra_node_type type)
{
  if (type == PRECOLORED)
    type = INITIAL;
  else if (type == SIMPLIFY)
    abort ();
  push_list_end (web->dlink, &WEBS(type));
  web->type = type;
}

/* Unlink WEB from the list it's currently on (which corresponds to
   its current type).  */

void
remove_web_from_list (struct web *web)
{
  if (web->type == PRECOLORED)
    remove_list (web->dlink, &WEBS(INITIAL));
  else
    remove_list (web->dlink, &WEBS(web->type));
}

/* Give MOVE the TYPE, and link it into the correct list.  */

static inline void
put_move (struct move *move, enum move_type type)
{
  switch (type)
    {
      case WORKLIST:
	push_list (move->dlink, &mv_worklist);
	break;
      case MV_COALESCED:
	push_list (move->dlink, &mv_coalesced);
	break;
      case CONSTRAINED:
	push_list (move->dlink, &mv_constrained);
	break;
      case FROZEN:
	push_list (move->dlink, &mv_frozen);
	break;
      case ACTIVE:
	push_list (move->dlink, &mv_active);
	break;
      default:
	abort ();
    }
  move->type = type;
}

/* Build the worklists we are going to process.  */

static void
build_worklists (struct df *df ATTRIBUTE_UNUSED)
{
  struct dlist *d, *d_next;
  struct move_list *ml;

  /* If we are not the first pass, put all stackwebs (which are still
     backed by a new pseudo, but conceptually can stand for a stackslot,
     i.e. it doesn't really matter if they get a color or not), on
     the SELECT stack first, those with lowest cost first.  This way
     they will be colored last, so do not constrain the coloring of the
     normal webs.  But still those with the highest count are colored
     before, i.e. get a color more probable.  The use of stackregs is
     a pure optimization, and all would work, if we used real stackslots
     from the begin.  */
  if (ra_pass > 1)
    {
      unsigned int i, num, max_num;
      struct web **order2web;
      max_num = num_webs - num_subwebs;
      order2web = xmalloc (max_num * sizeof (order2web[0]));
      for (i = 0, num = 0; i < max_num; i++)
	if (id2web[i]->regno >= max_normal_pseudo)
	  order2web[num++] = id2web[i];
      if (num)
	{
	  qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
	  for (i = num - 1;; i--)
	    {
	      struct web *web = order2web[i];
	      struct conflict_link *wl;
	      remove_list (web->dlink, &WEBS(INITIAL));
	      put_web (web, SELECT);
	      for (wl = web->conflict_list; wl; wl = wl->next)
		{
		  struct web *pweb = wl->t;
		  pweb->num_conflicts -= 1 + web->add_hardregs;
		}
	      if (i == 0)
		break;
	    }
	}
      free (order2web);
    }

  /* For all remaining initial webs, classify them.  */
  for (d = WEBS(INITIAL); d; d = d_next)
    {
      struct web *web = DLIST_WEB (d);
      d_next = d->next;
      if (web->type == PRECOLORED)
        continue;

      remove_list (d, &WEBS(INITIAL));
      if (web->num_conflicts >= NUM_REGS (web))
	put_web (web, SPILL);
      else if (web->moves)
	put_web (web, FREEZE);
      else
	put_web (web, SIMPLIFY);
    }

  /* And put all moves on the worklist for iterated coalescing.
     Note, that if iterated coalescing is off, then wl_moves doesn't
     contain any moves.  */
  for (ml = wl_moves; ml; ml = ml->next)
    if (ml->move)
      {
	struct move *m = ml->move;
        d = ra_calloc (sizeof (struct dlist));
        DLIST_MOVE (d) = m;
        m->dlink = d;
	put_move (m, WORKLIST);
      }
}

/* Enable the active moves, in which WEB takes part, to be processed.  */

static void
enable_move (struct web *web)
{
  struct move_list *ml;
  for (ml = web->moves; ml; ml = ml->next)
    if (ml->move->type == ACTIVE)
      {
	remove_list (ml->move->dlink, &mv_active);
	put_move (ml->move, WORKLIST);
      }
}

/* Decrement the degree of node WEB by the amount DEC.
   Possibly change the type of WEB, if the number of conflicts is
   now smaller than its freedom.  */

static void
decrement_degree (struct web *web, int dec)
{
  int before = web->num_conflicts;
  web->num_conflicts -= dec;
  if (web->num_conflicts < NUM_REGS (web) && before >= NUM_REGS (web))
    {
      struct conflict_link *a;
      enable_move (web);
      for (a = web->conflict_list; a; a = a->next)
	{
	  struct web *aweb = a->t;
	  if (aweb->type != SELECT && aweb->type != COALESCED)
	    enable_move (aweb);
	}
      if (web->type != FREEZE)
	{
	  remove_web_from_list (web);
	  if (web->moves)
	    put_web (web, FREEZE);
	  else
	    put_web (web, SIMPLIFY);
	}
    }
}

/* Repeatedly simplify the nodes on the simplify worklists.  */

static void
simplify (void)
{
  struct dlist *d;
  struct web *web;
  struct conflict_link *wl;
  while (1)
    {
      /* We try hard to color all the webs resulting from spills first.
	 Without that on register starved machines (x86 e.g) with some live
	 DImode pseudos, -fPIC, and an asm requiring %edx, it might be, that
	 we do rounds over rounds, because the conflict graph says, we can
	 simplify those short webs, but later due to irregularities we can't
	 color those pseudos.  So we have to spill them, which in later rounds
	 leads to other spills.  */
      d = pop_list (&WEBS(SIMPLIFY));
      if (!d)
	d = pop_list (&WEBS(SIMPLIFY_FAT));
      if (!d)
	d = pop_list (&WEBS(SIMPLIFY_SPILL));
      if (!d)
	break;
      web = DLIST_WEB (d);
      ra_debug_msg (DUMP_PROCESS, " simplifying web %3d, conflicts = %d\n",
		 web->id, web->num_conflicts);
      put_web (web, SELECT);
      for (wl = web->conflict_list; wl; wl = wl->next)
	{
	  struct web *pweb = wl->t;
	  if (pweb->type != SELECT && pweb->type != COALESCED)
	    {
	      decrement_degree (pweb, 1 + web->add_hardregs);
	    }
	}
    }
}

/* Helper function to remove a move from the movelist of the web.  */

static void
remove_move_1 (struct web *web, struct move *move)
{
  struct move_list *ml = web->moves;
  if (!ml)
    return;
  if (ml->move == move)
    {
      web->moves = ml->next;
      return;
    }
  for (; ml->next && ml->next->move != move; ml = ml->next) ;
  if (!ml->next)
    return;
  ml->next = ml->next->next;
}

/* Remove a move from the movelist of the web.  Actually this is just a
   wrapper around remove_move_1(), making sure, the removed move really is
   not in the list anymore.  */

static void
remove_move (struct web *web, struct move *move)
{
  struct move_list *ml;
  remove_move_1 (web, move);
  for (ml = web->moves; ml; ml = ml->next)
    if (ml->move == move)
      abort ();
}

/* Merge the moves for the two webs into the first web's movelist.  */

void
merge_moves (struct web *u, struct web *v)
{
  regset seen;
  struct move_list *ml, *ml_next;

  seen = BITMAP_XMALLOC ();
  for (ml = u->moves; ml; ml = ml->next)
    bitmap_set_bit (seen, INSN_UID (ml->move->insn));
  for (ml = v->moves; ml; ml = ml_next)
    {
      ml_next = ml->next;
      if (! bitmap_bit_p (seen, INSN_UID (ml->move->insn)))
        {
	  ml->next = u->moves;
	  u->moves = ml;
	}
    }
  BITMAP_XFREE (seen);
  v->moves = NULL;
}

/* Add a web to the simplify worklist, from the freeze worklist.  */

static void
add_worklist (struct web *web)
{
  if (web->type != PRECOLORED && !web->moves
      && web->num_conflicts < NUM_REGS (web))
    {
      remove_list (web->dlink, &WEBS(FREEZE));
      put_web (web, SIMPLIFY);
    }
}

/* Precolored node coalescing heuristic.  */

static int
ok (struct web *target, struct web *source)
{
  struct conflict_link *wl;
  int i;
  int color = source->color;
  int size;

  /* Normally one would think, the next test wouldn't be needed.
     We try to coalesce S and T, and S has already a color, and we checked
     when processing the insns, that both have the same mode.  So naively
     we could conclude, that of course that mode was valid for this color.
     Hah.  But there is sparc.  Before reload there are copy insns
     (e.g. the ones copying arguments to locals) which happily refer to
     colors in invalid modes.  We can't coalesce those things.  */
  if (! HARD_REGNO_MODE_OK (source->color, GET_MODE (target->orig_x)))
    return 0;

  /* Sanity for funny modes.  */
  size = hard_regno_nregs[color][GET_MODE (target->orig_x)];
  if (!size)
    return 0;

  /* We can't coalesce target with a precolored register which isn't in
     usable_regs.  */
  for (i = size; i--;)
    if (TEST_HARD_REG_BIT (never_use_colors, color + i)
	|| !TEST_HARD_REG_BIT (target->usable_regs, color + i)
	/* Before usually calling ok() at all, we already test, if the
	   candidates conflict in sup_igraph.  But when wide webs are
	   coalesced to hardregs, we only test the hardweb coalesced into.
	   This is only the begin color.  When actually coalescing both,
	   it will also take the following size colors, i.e. their webs.
	   We nowhere checked if the candidate possibly conflicts with
	   one of _those_, which is possible with partial conflicts,
	   so we simply do it here (this does one bit-test more than
	   necessary, the first color).  Note, that if X is precolored
	   bit [X*num_webs + Y] can't be set (see add_conflict_edge()).  */
	|| TEST_BIT (sup_igraph,
		     target->id * num_webs + hardreg2web[color + i]->id))
      return 0;

  for (wl = target->conflict_list; wl; wl = wl->next)
    {
      struct web *pweb = wl->t;
      if (pweb->type == SELECT || pweb->type == COALESCED)
	continue;

      /* Coalescing target (T) and source (S) is o.k, if for
	 all conflicts C of T it is true, that:
	  1) C will be colored, or
	  2) C is a hardreg (precolored), or
	  3) C already conflicts with S too, or
	  4) a web which contains C conflicts already with S.
	 XXX: we handle here only the special case of 4), that C is
	 a subreg, and the containing thing is the reg itself, i.e.
	 we dont handle the situation, were T conflicts with
	 (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
	 would be allowed also, as the S-conflict overlaps
	 the T-conflict.
         So, we first test the whole web for any of these conditions, and
         continue with the next C, if 1, 2 or 3 is true.  */
      if (pweb->num_conflicts < NUM_REGS (pweb)
	  || pweb->type == PRECOLORED
	  || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) )
	continue;

      /* This is reached, if not one of 1, 2 or 3 was true.  In the case C has
         no subwebs, 4 can't be true either, so we can't coalesce S and T.  */
      if (wl->sub == NULL)
        return 0;
      else
	{
	  /* The main webs do _not_ conflict, only some parts of both.  This
	     means, that 4 is possibly true, so we need to check this too.
	     For this we go through all sub conflicts between T and C, and see if
	     the target part of C already conflicts with S.  When this is not
	     the case we disallow coalescing.  */
	  struct sub_conflict *sl;
	  for (sl = wl->sub; sl; sl = sl->next)
	    {
              if (!TEST_BIT (igraph, igraph_index (source->id, sl->t->id)))
	        return 0;
	    }
        }
    }
  return 1;
}

/* Non-precolored node coalescing heuristic.  */

static int
conservative (struct web *target, struct web *source)
{
  unsigned int k;
  unsigned int loop;
  regset seen;
  struct conflict_link *wl;
  unsigned int num_regs = NUM_REGS (target); /* XXX */

  /* k counts the resulting conflict weight, if target and source
     would be merged, and all low-degree neighbors would be
     removed.  */
  k = 0 * MAX (target->add_hardregs, source->add_hardregs);
  seen = BITMAP_XMALLOC ();
  for (loop = 0; loop < 2; loop++)
    for (wl = ((loop == 0) ? target : source)->conflict_list;
	 wl; wl = wl->next)
      {
	struct web *pweb = wl->t;
	if (pweb->type != SELECT && pweb->type != COALESCED
	    && pweb->num_conflicts >= NUM_REGS (pweb)
	    && ! REGNO_REG_SET_P (seen, pweb->id))
	  {
	    SET_REGNO_REG_SET (seen, pweb->id);
	    k += 1 + pweb->add_hardregs;
	  }
      }
  BITMAP_XFREE (seen);

  if (k >= num_regs)
    return 0;
  return 1;
}

/* If the web is coalesced, return it's alias.  Otherwise, return what
   was passed in.  */

struct web *
alias (struct web *web)
{
  while (web->type == COALESCED)
    web = web->alias;
  return web;
}

/* Returns nonzero, if the TYPE belongs to one of those representing
   SIMPLIFY types.  */

static inline unsigned int
simplify_p (enum ra_node_type type)
{
  return type == SIMPLIFY || type == SIMPLIFY_SPILL || type == SIMPLIFY_FAT;
}

/* Actually combine two webs, that can be coalesced.  */

static void
combine (struct web *u, struct web *v)
{
  int i;
  struct conflict_link *wl;
  if (u == v || v->type == COALESCED)
    abort ();
  if ((u->regno >= max_normal_pseudo) != (v->regno >= max_normal_pseudo))
    abort ();
  remove_web_from_list (v);
  put_web (v, COALESCED);
  v->alias = u;
  u->is_coalesced = 1;
  v->is_coalesced = 1;
  u->num_aliased += 1 + v->num_aliased;
  if (flag_ra_merge_spill_costs && u->type != PRECOLORED)
    u->spill_cost += v->spill_cost;
    /*u->spill_cost = MAX (u->spill_cost, v->spill_cost);*/
  merge_moves (u, v);
  /* combine add_hardregs's of U and V.  */

  for (wl = v->conflict_list; wl; wl = wl->next)
    {
      struct web *pweb = wl->t;
      /* We don't strictly need to move conflicts between webs which are
	 already coalesced or selected, if we do iterated coalescing, or
	 better if we need not to be able to break aliases again.
	 I.e. normally we would use the condition
	 (pweb->type != SELECT && pweb->type != COALESCED).
	 But for now we simply merge all conflicts.  It doesn't take that
         much time.  */
      if (1)
	{
	  struct web *web = u;
	  int nregs = 1 + v->add_hardregs;
	  if (u->type == PRECOLORED)
	    nregs = hard_regno_nregs[u->color][GET_MODE (v->orig_x)];

	  /* For precolored U's we need to make conflicts between V's
	     neighbors and as many hardregs from U as V needed if it gets
	     color U.  For now we approximate this by V->add_hardregs, which
	     could be too much in multi-length classes.  We should really
	     count how many hardregs are needed for V with color U.  When U
	     isn't precolored this loop breaks out after one iteration.  */
	  for (i = 0; i < nregs; i++)
	    {
	      if (u->type == PRECOLORED)
		web = hardreg2web[i + u->color];
	      if (wl->sub == NULL)
		record_conflict (web, pweb);
	      else
		{
		  struct sub_conflict *sl;
		  /* So, between V and PWEB there are sub_conflicts.  We
		     need to relocate those conflicts to be between WEB (==
		     U when it wasn't precolored) and PWEB.  In the case
		     only a part of V conflicted with (part of) PWEB we
		     nevertheless make the new conflict between the whole U
		     and the (part of) PWEB.  Later we might try to find in
		     U the correct subpart corresponding (by size and
		     offset) to the part of V (sl->s) which was the source
		     of the conflict.  */
		  for (sl = wl->sub; sl; sl = sl->next)
		    {
		      /* Beware: sl->s is no subweb of web (== U) but of V.
			 We try to search a corresponding subpart of U.
			 If we found none we let it conflict with the whole U.
			 Note that find_subweb() only looks for mode and
			 subreg_byte of the REG rtx but not for the pseudo
			 reg number (otherwise it would be guaranteed to
			 _not_ find any subpart).  */
		      struct web *sweb = NULL;
		      if (SUBWEB_P (sl->s))
			sweb = find_subweb (web, sl->s->orig_x);
		      if (!sweb)
			sweb = web;
		      record_conflict (sweb, sl->t);
		    }
		}
	      if (u->type != PRECOLORED)
		break;
	    }
	  if (pweb->type != SELECT && pweb->type != COALESCED)
	    decrement_degree (pweb, 1 + v->add_hardregs);
	}
    }

  /* Now merge the usable_regs together.  */
  /* XXX That merging might normally make it necessary to
     adjust add_hardregs, which also means to adjust neighbors.  This can
     result in making some more webs trivially colorable, (or the opposite,
     if this increases our add_hardregs).  Because we intersect the
     usable_regs it should only be possible to decrease add_hardregs.  So a
     conservative solution for now is to simply don't change it.  */
  u->use_my_regs = 1;
  AND_HARD_REG_SET (u->usable_regs, v->usable_regs);
  u->regclass = reg_class_subunion[u->regclass][v->regclass];
  /* Count number of possible hardregs.  This might make U a spillweb,
     but that could also happen, if U and V together had too many
     conflicts.  */
  u->num_freedom = hard_regs_count (u->usable_regs);
  u->num_freedom -= u->add_hardregs;
  /* The next would mean an invalid coalesced move (both webs have no
     possible hardreg in common), so abort.  */
  if (!u->num_freedom)
    abort();

  if (u->num_conflicts >= NUM_REGS (u)
      && (u->type == FREEZE || simplify_p (u->type)))
    {
      remove_web_from_list (u);
      put_web (u, SPILL);
    }

  /* We want the most relaxed combination of spill_temp state.
     I.e. if any was no spilltemp or a spilltemp2, the result is so too,
     otherwise if any is short, the result is too.  It remains, when both
     are normal spilltemps.  */
  if (v->spill_temp == 0)
    u->spill_temp = 0;
  else if (v->spill_temp == 2 && u->spill_temp != 0)
    u->spill_temp = 2;
  else if (v->spill_temp == 3 && u->spill_temp == 1)
    u->spill_temp = 3;
}

/* Attempt to coalesce the first thing on the move worklist.
   This is used only for iterated coalescing.  */

static void
coalesce (void)
{
  struct dlist *d = pop_list (&mv_worklist);
  struct move *m = DLIST_MOVE (d);
  struct web *source = alias (m->source_web);
  struct web *target = alias (m->target_web);

  if (target->type == PRECOLORED)
    {
      struct web *h = source;
      source = target;
      target = h;
    }
  if (source == target)
    {
      remove_move (source, m);
      put_move (m, MV_COALESCED);
      add_worklist (source);
    }
  else if (target->type == PRECOLORED
	   || TEST_BIT (sup_igraph, source->id * num_webs + target->id)
	   || TEST_BIT (sup_igraph, target->id * num_webs + source->id)
	   || !ok_class (target, source))
    {
      remove_move (source, m);
      remove_move (target, m);
      put_move (m, CONSTRAINED);
      add_worklist (source);
      add_worklist (target);
    }
  else if ((source->type == PRECOLORED && ok (target, source))
	   || (source->type != PRECOLORED
	       && conservative (target, source)))
    {
      remove_move (source, m);
      remove_move (target, m);
      put_move (m, MV_COALESCED);
      combine (source, target);
      add_worklist (source);
    }
  else
    put_move (m, ACTIVE);
}

/* Freeze the moves associated with the web.  Used for iterated coalescing.  */

static void
freeze_moves (struct web *web)
{
  struct move_list *ml, *ml_next;
  for (ml = web->moves; ml; ml = ml_next)
    {
      struct move *m = ml->move;
      struct web *src, *dest;
      ml_next = ml->next;
      if (m->type == ACTIVE)
	remove_list (m->dlink, &mv_active);
      else
	remove_list (m->dlink, &mv_worklist);
      put_move (m, FROZEN);
      remove_move (web, m);
      src = alias (m->source_web);
      dest = alias (m->target_web);
      src = (src == web) ? dest : src;
      remove_move (src, m);
      /* XXX GA use the original v, instead of alias(v) */
      if (!src->moves && src->num_conflicts < NUM_REGS (src))
	{
	  remove_list (src->dlink, &WEBS(FREEZE));
	  put_web (src, SIMPLIFY);
	}
    }
}

/* Freeze the first thing on the freeze worklist (only for iterated
   coalescing).  */

static void
freeze (void)
{
  struct dlist *d = pop_list (&WEBS(FREEZE));
  put_web (DLIST_WEB (d), SIMPLIFY);
  freeze_moves (DLIST_WEB (d));
}

/* The current spill heuristic.  Returns a number for a WEB.
   Webs with higher numbers are selected later.  */

static unsigned HOST_WIDE_INT (*spill_heuristic) (struct web *);

static unsigned HOST_WIDE_INT default_spill_heuristic (struct web *);

/* Our default heuristic is similar to spill_cost / num_conflicts.
   Just scaled for integer arithmetic, and it favors coalesced webs,
   and webs which span more insns with deaths.  */

static unsigned HOST_WIDE_INT
default_spill_heuristic (struct web *web)
{
  unsigned HOST_WIDE_INT ret;
  unsigned int divisor = 1;
  /* Make coalesce targets cheaper to spill, because they will be broken
     up again into smaller parts.  */
  if (flag_ra_break_aliases)
    divisor += web->num_aliased;
  divisor += web->num_conflicts;
  ret = ((web->spill_cost << 8) + divisor - 1) / divisor;
  /* It is better to spill webs that span more insns (deaths in our
     case) than other webs with the otherwise same spill_cost.  So make
     them a little bit cheaper.  Remember that spill_cost is unsigned.  */
  if (web->span_deaths < ret)
    ret -= web->span_deaths;
  return ret;
}

/* Select the cheapest spill to be potentially spilled (we don't
   *actually* spill until we need to).  */

static void
select_spill (void)
{
  unsigned HOST_WIDE_INT best = (unsigned HOST_WIDE_INT) -1;
  struct dlist *bestd = NULL;
  unsigned HOST_WIDE_INT best2 = (unsigned HOST_WIDE_INT) -1;
  struct dlist *bestd2 = NULL;
  struct dlist *d;
  for (d = WEBS(SPILL); d; d = d->next)
    {
      struct web *w = DLIST_WEB (d);
      unsigned HOST_WIDE_INT cost = spill_heuristic (w);
      if ((!w->spill_temp) && cost < best)
	{
	  best = cost;
	  bestd = d;
	}
      /* Specially marked spill temps can be spilled.  Also coalesce
	 targets can.  Eventually they will be broken up later in the
	 colorizing process, so if we have nothing better take that.  */
      else if ((w->spill_temp == 2 || w->is_coalesced) && cost < best2)
	{
	  best2 = cost;
	  bestd2 = d;
	}
    }
  if (!bestd)
    {
      bestd = bestd2;
      best = best2;
    }
  if (!bestd)
    abort ();

  /* Note the potential spill.  */
  DLIST_WEB (bestd)->was_spilled = 1;
  remove_list (bestd, &WEBS(SPILL));
  put_web (DLIST_WEB (bestd), SIMPLIFY);
  freeze_moves (DLIST_WEB (bestd));
  ra_debug_msg (DUMP_PROCESS, " potential spill web %3d, conflicts = %d\n",
	     DLIST_WEB (bestd)->id, DLIST_WEB (bestd)->num_conflicts);
}

/* Given a set of forbidden colors to begin at, and a set of still
   free colors, and MODE, returns nonzero of color C is still usable.  */

static int
color_usable_p (int c, HARD_REG_SET dont_begin_colors,
		HARD_REG_SET free_colors, enum machine_mode  mode)
{
  if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
      && TEST_HARD_REG_BIT (free_colors, c)
      && HARD_REGNO_MODE_OK (c, mode))
    {
      int i, size;
      size = hard_regno_nregs[c][mode];
      for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
      if (i == size)
	return 1;
    }
  return 0;
}

/* I don't want to clutter up the actual code with ifdef's.  */
#ifdef REG_ALLOC_ORDER
#define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c]
#else
#define INV_REG_ALLOC_ORDER(c) c
#endif

/* Searches in FREE_COLORS for a block of hardregs of the right length
   for MODE, which doesn't begin at a hardreg mentioned in DONT_BEGIN_COLORS.
   If it needs more than one hardreg it prefers blocks beginning
   at an even hardreg, and only gives an odd begin reg if no other
   block could be found.  */

int
get_free_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET free_colors,
	      enum machine_mode mode)
{
  int c;
  int last_resort_reg = -1;
  int pref_reg = -1;
  int pref_reg_order = INT_MAX;
  int last_resort_reg_order = INT_MAX;

  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
    if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
	&& TEST_HARD_REG_BIT (free_colors, c)
	&& HARD_REGNO_MODE_OK (c, mode))
      {
	int i, size;
	size = hard_regno_nregs[c][mode];
	for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
	if (i != size)
	  {
	    c += i;
	    continue;
	  }
	if (i == size)
	  {
	    if (size < 2 || (c & 1) == 0)
	      {
		if (INV_REG_ALLOC_ORDER (c) < pref_reg_order)
		  {
		    pref_reg = c;
		    pref_reg_order = INV_REG_ALLOC_ORDER (c);
		  }
	      }
	    else if (INV_REG_ALLOC_ORDER (c) < last_resort_reg_order)
	      {
		last_resort_reg = c;
		last_resort_reg_order = INV_REG_ALLOC_ORDER (c);
	      }
	  }
	else
	  c += i;
      }
  return pref_reg >= 0 ? pref_reg : last_resort_reg;
}

/* Similar to get_free_reg(), but first search in colors provided
   by BIAS _and_ PREFER_COLORS, then in BIAS alone, then in PREFER_COLORS
   alone, and only then for any free color.  If flag_ra_biased is zero
   only do the last two steps.  */

static int
get_biased_reg (HARD_REG_SET dont_begin_colors, HARD_REG_SET bias,
		HARD_REG_SET prefer_colors, HARD_REG_SET free_colors,
		enum machine_mode mode)
{
  int c = -1;
  HARD_REG_SET s;
  if (flag_ra_biased)
    {
      COPY_HARD_REG_SET (s, dont_begin_colors);
      IOR_COMPL_HARD_REG_SET (s, bias);
      IOR_COMPL_HARD_REG_SET (s, prefer_colors);
      c = get_free_reg (s, free_colors, mode);
      if (c >= 0)
	return c;
      COPY_HARD_REG_SET (s, dont_begin_colors);
      IOR_COMPL_HARD_REG_SET (s, bias);
      c = get_free_reg (s, free_colors, mode);
      if (c >= 0)
	return c;
    }
  COPY_HARD_REG_SET (s, dont_begin_colors);
  IOR_COMPL_HARD_REG_SET (s, prefer_colors);
  c = get_free_reg (s, free_colors, mode);
  if (c >= 0)
      return c;
  c = get_free_reg (dont_begin_colors, free_colors, mode);
  return c;
}

/* Counts the number of non-overlapping bitblocks of length LEN
   in FREE_COLORS.  */

static int
count_long_blocks (HARD_REG_SET free_colors, int len)
{
  int i, j;
  int count = 0;
  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    {
      if (!TEST_HARD_REG_BIT (free_colors, i))
	continue;
      for (j = 1; j < len; j++)
	if (!TEST_HARD_REG_BIT (free_colors, i + j))
	  break;
      /* Bits [i .. i+j-1] are free.  */
      if (j == len)
	count++;
      i += j - 1;
    }
  return count;
}

/* Given a hardreg set S, return a string representing it.
   Either as 0/1 string, or as hex value depending on the implementation
   of hardreg sets.  Note that this string is statically allocated.  */

static char *
hardregset_to_string (HARD_REG_SET s)
{
  static char string[/*FIRST_PSEUDO_REGISTER + 30*/1024];
#if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDE_INT
  sprintf (string, HOST_WIDE_INT_PRINT_HEX, s);
#else
  char *c = string;
  int i,j;
  c += sprintf (c, "{ ");
  for (i = 0;i < HARD_REG_SET_LONGS; i++)
    {
      for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
	  c += sprintf (c, "%s", ( 1 << j) & s[i] ? "1" : "0");
      c += sprintf (c, "%s", i ? ", " : "");
    }
  c += sprintf (c, " }");
#endif
  return string;
}

/* For WEB, look at its already colored neighbors, and calculate
   the set of hardregs which is not allowed as color for WEB.  Place
   that set int *RESULT.  Note that the set of forbidden begin colors
   is not the same as all colors taken up by neighbors.  E.g. suppose
   two DImode webs, but only the lo-part from one conflicts with the
   hipart from the other, and suppose the other gets colors 2 and 3
   (it needs two SImode hardregs).  Now the first can take also color
   1 or 2, although in those cases there's a partial overlap.  Only
   3 can't be used as begin color.  */

static void
calculate_dont_begin (struct web *web, HARD_REG_SET *result)
{
  struct conflict_link *wl;
  HARD_REG_SET dont_begin;
  /* The bits set in dont_begin correspond to the hardregs, at which
     WEB may not begin.  This differs from the set of _all_ hardregs which
     are taken by WEB's conflicts in the presence of wide webs, where only
     some parts conflict with others.  */
  CLEAR_HARD_REG_SET (dont_begin);
  for (wl = web->conflict_list; wl; wl = wl->next)
    {
      struct web *w;
      struct web *ptarget = alias (wl->t);
      struct sub_conflict *sl = wl->sub;
      w = sl ? sl->t : wl->t;
      while (w)
	{
	  if (ptarget->type == COLORED || ptarget->type == PRECOLORED)
	    {
	      struct web *source = (sl) ? sl->s : web;
	      unsigned int tsize = hard_regno_nregs[ptarget->color]
						   [GET_MODE (w->orig_x)];
	      /* ssize is only a first guess for the size.  */
	      unsigned int ssize = hard_regno_nregs[ptarget->color][GET_MODE
					            (source->orig_x)];
	      unsigned int tofs = 0;
	      unsigned int sofs = 0;
	      /* C1 and C2 can become negative, so unsigned
		 would be wrong.  */
	      int c1, c2;

	      if (SUBWEB_P (w)
		  && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
		tofs = (SUBREG_BYTE (w->orig_x) / UNITS_PER_WORD);
	      if (SUBWEB_P (source)
		  && GET_MODE_SIZE (GET_MODE (source->orig_x))
		     >= UNITS_PER_WORD)
		sofs = (SUBREG_BYTE (source->orig_x) / UNITS_PER_WORD);
	      c1 = ptarget->color + tofs - sofs - ssize + 1;
	      c2 = ptarget->color + tofs + tsize - 1 - sofs;
	      if (c2 >= 0)
		{
		  if (c1 < 0)
		    c1 = 0;
		  /* Because ssize was only guessed above, which influenced our
		     begin color (c1), we need adjustment, if for that color
		     another size would be needed.  This is done by moving
		     c1 to a place, where the last of sources hardregs does not
		     overlap the first of targets colors.  */
		  while (c1 + sofs
			 + hard_regno_nregs[c1][GET_MODE (source->orig_x)] - 1
			 < ptarget->color + tofs)
		    c1++;
		  while (c1 > 0 && c1 + sofs
			 + hard_regno_nregs[c1][GET_MODE (source->orig_x)] - 1
			 > ptarget->color + tofs)
		    c1--;
		  for (; c1 <= c2; c1++)
		    SET_HARD_REG_BIT (dont_begin, c1);
		}
	    }
	  /* The next if() only gets true, if there was no wl->sub at all, in
	     which case we are only making one go through this loop with W being
	     a whole web.  */
	  if (!sl)
	    break;
	  sl = sl->next;
	  w = sl ? sl->t : NULL;
	}
    }
  COPY_HARD_REG_SET (*result, dont_begin);
}

/* Try to assign a color to WEB.  If HARD if nonzero, we try many
   tricks to get it one color, including respilling already colored
   neighbors.

   We also trie very hard, to not constrain the uncolored non-spill
   neighbors, which need more hardregs than we.  Consider a situation, 2
   hardregs free for us (0 and 1), and one of our neighbors needs 2
   hardregs, and only conflicts with us.  There are 3 hardregs at all.  Now
   a simple minded method might choose 1 as color for us.  Then our neighbor
   has two free colors (0 and 2) as it should, but they are not consecutive,
   so coloring it later would fail.  This leads to nasty problems on
   register starved machines, so we try to avoid this.  */

static void
colorize_one_web (struct web *web, int hard)
{
  struct conflict_link *wl;
  HARD_REG_SET colors, dont_begin;
  int c = -1;
  int bestc = -1;
  int neighbor_needs= 0;
  struct web *fats_parent = NULL;
  int num_fat = 0;
  int long_blocks = 0;
  int best_long_blocks = -1;
  HARD_REG_SET fat_colors;
  HARD_REG_SET bias;

  CLEAR_HARD_REG_SET (fat_colors);
  
  if (web->regno >= max_normal_pseudo)
    hard = 0;

  /* First we want to know the colors at which we can't begin.  */
  calculate_dont_begin (web, &dont_begin);
  CLEAR_HARD_REG_SET (bias);

  /* Now setup the set of colors used by our neighbors neighbors,
     and search the biggest noncolored neighbor.  */
  neighbor_needs = web->add_hardregs + 1;
  for (wl = web->conflict_list; wl; wl = wl->next)
    {
      struct web *w;
      struct web *ptarget = alias (wl->t);
      struct sub_conflict *sl = wl->sub;
      IOR_HARD_REG_SET (bias, ptarget->bias_colors);
      w = sl ? sl->t : wl->t;
      if (ptarget->type != COLORED && ptarget->type != PRECOLORED
	  && !ptarget->was_spilled)
        while (w)
	  {
	    if (find_web_for_subweb (w)->type != COALESCED
		&& w->add_hardregs >= neighbor_needs)
	      {
		neighbor_needs = w->add_hardregs;
		fats_parent = ptarget;
		num_fat++;
	      }
	    if (!sl)
	      break;
	    sl = sl->next;
	    w = sl ? sl->t : NULL;
	  }
    }

  ra_debug_msg (DUMP_COLORIZE, "colorize web %d [don't begin at %s]", web->id,
             hardregset_to_string (dont_begin));

  /* If there are some fat neighbors, remember their usable regs,
     and how many blocks are free in it for that neighbor.  */
  if (num_fat)
    {
      COPY_HARD_REG_SET (fat_colors, fats_parent->usable_regs);
      long_blocks = count_long_blocks (fat_colors, neighbor_needs + 1);
    }

  /* We break out, if we found a color which doesn't constrain
     neighbors, or if we can't find any colors.  */
  while (1)
    {
      HARD_REG_SET call_clobbered;

      /* Here we choose a hard-reg for the current web.  For non spill
         temporaries we first search in the hardregs for it's preferred
	 class, then, if we found nothing appropriate, in those of the
	 alternate class.  For spill temporaries we only search in
	 usable_regs of this web (which is probably larger than that of
	 the preferred or alternate class).  All searches first try to
	 find a non-call-clobbered hard-reg.
         XXX this should be more finegraned... First look into preferred
         non-callclobbered hardregs, then _if_ the web crosses calls, in
         alternate non-cc hardregs, and only _then_ also in preferred cc
         hardregs (and alternate ones).  Currently we don't track the number
         of calls crossed for webs.  We should.  */
      if (web->use_my_regs)
	{
	  COPY_HARD_REG_SET (colors, web->usable_regs);
	  AND_HARD_REG_SET (colors,
			    usable_regs[reg_preferred_class (web->regno)]);
	}
      else
	COPY_HARD_REG_SET (colors,
			   usable_regs[reg_preferred_class (web->regno)]);
#ifdef CANNOT_CHANGE_MODE_CLASS
      if (web->mode_changed)
        AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs);
#endif
      COPY_HARD_REG_SET (call_clobbered, colors);
      AND_HARD_REG_SET (call_clobbered, call_used_reg_set);

      /* If this web got a color in the last pass, try to give it the
	 same color again.  This will to much better colorization
	 down the line, as we spilled for a certain coloring last time.  */
      if (web->old_color)
	{
	  c = web->old_color - 1;
	  if (!color_usable_p (c, dont_begin, colors,
			       PSEUDO_REGNO_MODE (web->regno)))
	    c = -1;
	}
      else
	c = -1;
      if (c < 0)
	c = get_biased_reg (dont_begin, bias, web->prefer_colors,
			    call_clobbered, PSEUDO_REGNO_MODE (web->regno));
      if (c < 0)
	c = get_biased_reg (dont_begin, bias, web->prefer_colors,
			  colors, PSEUDO_REGNO_MODE (web->regno));

      if (c < 0)
	{
	  if (web->use_my_regs)
	    IOR_HARD_REG_SET (colors, web->usable_regs);
	  else
	    IOR_HARD_REG_SET (colors, usable_regs
			      [reg_alternate_class (web->regno)]);
#ifdef CANNOT_CHANGE_MODE_CLASS
	  if (web->mode_changed)
	    AND_COMPL_HARD_REG_SET (colors, invalid_mode_change_regs);
#endif
	  COPY_HARD_REG_SET (call_clobbered, colors);
	  AND_HARD_REG_SET (call_clobbered, call_used_reg_set);

	  c = get_biased_reg (dont_begin, bias, web->prefer_colors,
			    call_clobbered, PSEUDO_REGNO_MODE (web->regno));
	  if (c < 0)
	    c = get_biased_reg (dont_begin, bias, web->prefer_colors,
			      colors, PSEUDO_REGNO_MODE (web->regno));
	}
      if (c < 0)
	break;
      if (bestc < 0)
        bestc = c;
      /* If one of the yet uncolored neighbors, which is not a potential
	 spill needs a block of hardregs be sure, not to destroy such a block
	 by coloring one reg in the middle.  */
      if (num_fat)
	{
	  int i;
	  int new_long;
	  HARD_REG_SET colors1;
	  COPY_HARD_REG_SET (colors1, fat_colors);
	  for (i = 0; i < 1 + web->add_hardregs; i++)
	    CLEAR_HARD_REG_BIT (colors1, c + i);
	  new_long = count_long_blocks (colors1, neighbor_needs + 1);
	  /* If we changed the number of long blocks, and it's now smaller
	     than needed, we try to avoid this color.  */
	  if (long_blocks != new_long && new_long < num_fat)
	    {
	      if (new_long > best_long_blocks)
		{
		  best_long_blocks = new_long;
		  bestc = c;
		}
	      SET_HARD_REG_BIT (dont_begin, c);
	      ra_debug_msg (DUMP_COLORIZE, " avoid %d", c);
	    }
	  else
	    /* We found a color which doesn't destroy a block.  */
	    break;
	}
      /* If we havee no fat neighbors, the current color won't become
	 "better", so we've found it.  */
      else
	break;
    }
  ra_debug_msg (DUMP_COLORIZE, " --> got %d", c < 0 ? bestc : c);
  if (bestc >= 0 && c < 0 && !web->was_spilled)
    {
      /* This is a non-potential-spill web, which got a color, which did
	 destroy a hardreg block for one of it's neighbors.  We color
	 this web anyway and hope for the best for the neighbor, if we are
	 a spill temp.  */
      if (1 || web->spill_temp)
        c = bestc;
      ra_debug_msg (DUMP_COLORIZE, " [constrains neighbors]");
    }
  ra_debug_msg (DUMP_COLORIZE, "\n");

  if (c < 0)
    {
      /* Guard against a simplified node being spilled.  */
      /* Don't abort.  This can happen, when e.g. enough registers
	 are available in colors, but they are not consecutive.  This is a
	 very serious issue if this web is a short live one, because
	 even if we spill this one here, the situation won't become better
	 in the next iteration.  It probably will have the same conflicts,
	 those will have the same colors, and we would come here again, for
	 all parts, in which this one gets split by the spill.  This
	 can result in endless iteration spilling the same register again and
	 again.  That's why we try to find a neighbor, which spans more
	 instructions that ourself, and got a color, and try to spill _that_.

	 if (DLIST_WEB (d)->was_spilled < 0)
	 abort (); */
      if (hard && (!web->was_spilled || web->spill_temp))
	{
	  unsigned int loop;
	  struct web *try = NULL;
	  struct web *candidates[8];

	  ra_debug_msg (DUMP_COLORIZE, "  *** %d spilled, although %s ***\n",
		     web->id, web->spill_temp ? "spilltemp" : "non-spill");
	  /* We make multiple passes over our conflicts, first trying to
	     spill those webs, which only got a color by chance, but
	     were potential spill ones, and if that isn't enough, in a second
	     pass also to spill normal colored webs.  If we still didn't find
	     a candidate, but we are a spill-temp, we make a third pass
	     and include also webs, which were targets for coalescing, and
	     spill those.  */
	  memset (candidates, 0, sizeof candidates);
#define set_cand(i, w) \
	  do { \
	      if (!candidates[(i)] \
		  || (candidates[(i)]->spill_cost < (w)->spill_cost)) \
		candidates[(i)] = (w); \
	  } while (0)
	  for (wl = web->conflict_list; wl; wl = wl->next)
	    {
	      struct web *w = wl->t;
	      struct web *aw = alias (w);
	      /* If we are a spill-temp, we also look at webs coalesced
		 to precolored ones.  Otherwise we only look at webs which
		 themselves were colored, or coalesced to one.  */
	      if (aw->type == PRECOLORED && w != aw && web->spill_temp
		  && flag_ra_optimistic_coalescing)
		{
		  if (!w->spill_temp)
		    set_cand (4, w);
		  else if (web->spill_temp == 2
			   && w->spill_temp == 2
			   && w->spill_cost < web->spill_cost)
		    set_cand (5, w);
		  else if (web->spill_temp != 2
			   && (w->spill_temp == 2
			       || w->spill_cost < web->spill_cost))
		    set_cand (6, w);
		  continue;
		}
	      if (aw->type != COLORED)
		continue;
	      if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
		  && w->was_spilled)
		{
		  if (w->spill_cost < web->spill_cost)
		    set_cand (0, w);
		  else if (web->spill_temp)
		    set_cand (1, w);
		}
	      if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
		  && !w->was_spilled)
		{
		  if (w->spill_cost < web->spill_cost)
		    set_cand (2, w);
		  else if (web->spill_temp && web->spill_temp != 2)
		    set_cand (3, w);
		}
	      if (web->spill_temp)
		{
		  if (w->type == COLORED && w->spill_temp == 2
		      && !w->is_coalesced
		      && (w->spill_cost < web->spill_cost
			  || web->spill_temp != 2))
		    set_cand (4, w);
		  if (!aw->spill_temp)
		    set_cand (5, aw);
		  if (aw->spill_temp == 2
		      && (aw->spill_cost < web->spill_cost
			  || web->spill_temp != 2))
		    set_cand (6, aw);
		  /* For boehm-gc/misc.c.  If we are a difficult spilltemp,
		     also coalesced neighbors are a chance, _even_ if they
		     too are spilltemps.  At least their coalescing can be
		     broken up, which may be reset usable_regs, and makes
		     it easier colorable.  */
		  if (web->spill_temp != 2 && aw->is_coalesced
		      && flag_ra_optimistic_coalescing)
		    set_cand (7, aw);
		}
	    }
	  for (loop = 0; try == NULL && loop < 8; loop++)
	    if (candidates[loop])
	      try = candidates[loop];
#undef set_cand
	  if (try)
	    {
	      int old_c = try->color;
	      if (try->type == COALESCED)
		{
		  if (alias (try)->type != PRECOLORED)
		    abort ();
		  ra_debug_msg (DUMP_COLORIZE, "  breaking alias %d -> %d\n",
			     try->id, alias (try)->id);
		  break_precolored_alias (try);
		  colorize_one_web (web, hard);
		}
	      else
		{
		  remove_list (try->dlink, &WEBS(COLORED));
		  put_web (try, SPILLED);
		  /* Now try to colorize us again.  Can recursively make other
		     webs also spill, until there are no more unspilled
		     neighbors.  */
		  ra_debug_msg (DUMP_COLORIZE, "  trying to spill %d\n", try->id);
		  colorize_one_web (web, hard);
		  if (web->type != COLORED)
		    {
		      /* We tried recursively to spill all already colored
			 neighbors, but we are still uncolorable.  So it made
			 no sense to spill those neighbors.  Recolor them.  */
		      remove_list (try->dlink, &WEBS(SPILLED));
		      put_web (try, COLORED);
		      try->color = old_c;
		      ra_debug_msg (DUMP_COLORIZE,
				    "  spilling %d was useless\n", try->id);
		    }
		  else
		    {
		      ra_debug_msg (DUMP_COLORIZE,
				    "  to spill %d was a good idea\n",
				    try->id);
		      remove_list (try->dlink, &WEBS(SPILLED));
		      if (try->was_spilled)
			colorize_one_web (try, 0);
		      else
			colorize_one_web (try, hard - 1);
		    }
		}
	    }
	  else
	    /* No more chances to get a color, so give up hope and
	       spill us.  */
	    put_web (web, SPILLED);
	}
      else
        put_web (web, SPILLED);
    }
  else
    {
      put_web (web, COLORED);
      web->color = c;
      if (flag_ra_biased)
	{
	  int nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
	  for (wl = web->conflict_list; wl; wl = wl->next)
	    {
	      struct web *ptarget = alias (wl->t);
	      int i;
	      for (i = 0; i < nregs; i++)
		SET_HARD_REG_BIT (ptarget->bias_colors, c + i);
	    }
	}
    }
  if (web->regno >= max_normal_pseudo && web->type == SPILLED)
    {
      web->color = an_unusable_color;
      remove_list (web->dlink, &WEBS(SPILLED));
      put_web (web, COLORED);
    }
  if (web->type == SPILLED && flag_ra_optimistic_coalescing
      && web->is_coalesced)
    {
      ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
      restore_conflicts_from_coalesce (web);
      break_aliases_to_web (web);
      insert_coalesced_conflicts ();
      ra_debug_msg (DUMP_COLORIZE, "\n");
      remove_list (web->dlink, &WEBS(SPILLED));
      put_web (web, SELECT);
      web->color = -1;
    }
}

/* Assign the colors to all nodes on the select stack.  And update the
   colors of coalesced webs.  */

static void
assign_colors (void)
{
  struct dlist *d;

  while (WEBS(SELECT))
    {
      d = pop_list (&WEBS(SELECT));
      colorize_one_web (DLIST_WEB (d), 1);
    }

  for (d = WEBS(COALESCED); d; d = d->next)
    {
      struct web *a = alias (DLIST_WEB (d));
      DLIST_WEB (d)->color = a->color;
    }
}

/* WEB is a spilled web.  Look if we can improve the cost of the graph,
   by coloring WEB, even if we then need to spill some of it's neighbors.
   For this we calculate the cost for each color C, that results when we
   _would_ give WEB color C (i.e. the cost of the then spilled neighbors).
   If the lowest cost among them is smaller than the spillcost of WEB, we
   do that recoloring, and instead spill the neighbors.

   This can sometime help, when due to irregularities in register file,
   and due to multi word pseudos, the colorization is suboptimal.  But
   be aware, that currently this pass is quite slow.  */

static void
try_recolor_web (struct web *web)
{
  struct conflict_link *wl;
  unsigned HOST_WIDE_INT *cost_neighbors;
  unsigned int *min_color;
  int newcol, c;
  HARD_REG_SET precolored_neighbors, spill_temps;
  HARD_REG_SET possible_begin, wide_seen;
  cost_neighbors = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (cost_neighbors[0]));
  /* For each hard-regs count the number of preceding hardregs, which
     would overlap this color, if used in WEB's mode.  */
  min_color = xcalloc (FIRST_PSEUDO_REGISTER, sizeof (int));
  CLEAR_HARD_REG_SET (possible_begin);
  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
    {
      int i, nregs;
      if (!HARD_REGNO_MODE_OK (c, GET_MODE (web->orig_x)))
	continue;
      nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
      for (i = 0; i < nregs; i++)
	if (!TEST_HARD_REG_BIT (web->usable_regs, c + i))
	  break;
      if (i < nregs || nregs == 0)
	continue;
      SET_HARD_REG_BIT (possible_begin, c);
      for (; nregs--;)
	if (!min_color[c + nregs])
	  min_color[c + nregs] = 1 + c;
    }
  CLEAR_HARD_REG_SET (precolored_neighbors);
  CLEAR_HARD_REG_SET (spill_temps);
  CLEAR_HARD_REG_SET (wide_seen);
  for (wl = web->conflict_list; wl; wl = wl->next)
    {
      HARD_REG_SET dont_begin;
      struct web *web2 = alias (wl->t);
      struct conflict_link *nn;
      int c1, c2;
      int wide_p = 0;
      if (wl->t->type == COALESCED || web2->type != COLORED)
	{
	  if (web2->type == PRECOLORED)
	    {
	      c1 = min_color[web2->color];
	      c1 = (c1 == 0) ? web2->color : (c1 - 1);
	      c2 = web2->color;
	      for (; c1 <= c2; c1++)
	        SET_HARD_REG_BIT (precolored_neighbors, c1);
	    }
	  continue;
	}
      /* Mark colors for which some wide webs are involved.  For
	 those the independent sets are not simply one-node graphs, so
	 they can't be recolored independent from their neighborhood.  This
	 means, that our cost calculation can be incorrect (assuming it
	 can avoid spilling a web because it thinks some colors are available,
	 although it's neighbors which itself need recoloring might take
	 away exactly those colors).  */
      if (web2->add_hardregs)
	wide_p = 1;
      for (nn = web2->conflict_list; nn && !wide_p; nn = nn->next)
	if (alias (nn->t)->add_hardregs)
	  wide_p = 1;
      calculate_dont_begin (web2, &dont_begin);
      c1 = min_color[web2->color];
      /* Note that min_color[] contains 1-based values (zero means
	 undef).  */
      c1 = c1 == 0 ? web2->color : (c1 - 1);
      c2 = web2->color + hard_regno_nregs[web2->color][GET_MODE
					  (web2->orig_x)] - 1;
      for (; c1 <= c2; c1++)
	if (TEST_HARD_REG_BIT (possible_begin, c1))
	  {
	    int nregs;
	    HARD_REG_SET colors;
	    nregs = hard_regno_nregs[c1][GET_MODE (web->orig_x)];
	    COPY_HARD_REG_SET (colors, web2->usable_regs);
	    for (; nregs--;)
	      CLEAR_HARD_REG_BIT (colors, c1 + nregs);
	    if (wide_p)
	      SET_HARD_REG_BIT (wide_seen, c1);
	    if (get_free_reg (dont_begin, colors,
			      GET_MODE (web2->orig_x)) < 0)
	      {
		if (web2->spill_temp)
		  SET_HARD_REG_BIT (spill_temps, c1);
		else
		  cost_neighbors[c1] += web2->spill_cost;
	      }
	  }
    }
  newcol = -1;
  for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
    if (TEST_HARD_REG_BIT (possible_begin, c)
	&& !TEST_HARD_REG_BIT (precolored_neighbors, c)
	&& !TEST_HARD_REG_BIT (spill_temps, c)
	&& (newcol == -1
	    || cost_neighbors[c] < cost_neighbors[newcol]))
      newcol = c;
  if (newcol >= 0 && cost_neighbors[newcol] < web->spill_cost)
    {
      int nregs = hard_regno_nregs[newcol][GET_MODE (web->orig_x)];
      unsigned HOST_WIDE_INT cost = 0;
      int *old_colors;
      struct conflict_link *wl_next;
      ra_debug_msg (DUMP_COLORIZE, "try to set web %d to color %d\n", web->id,
		 newcol);
      remove_list (web->dlink, &WEBS(SPILLED));
      put_web (web, COLORED);
      web->color = newcol;
      old_colors = xcalloc (num_webs, sizeof (int));
      for (wl = web->conflict_list; wl; wl = wl_next)
	{
	  struct web *web2 = alias (wl->t);
	  /* If web2 is a coalesce-target, and will become spilled
	     below in colorize_one_web(), and the current conflict wl
	     between web and web2 was only the result of that coalescing
	     this conflict will be deleted, making wl invalid.  So save
	     the next conflict right now.  Note that if web2 has indeed
	     such state, then wl->next can not be deleted in this
	     iteration.  */
	  wl_next = wl->next;
	  if (web2->type == COLORED)
	    {
	      int nregs2 = hard_regno_nregs[web2->color][GET_MODE
					    (web2->orig_x)];
	      if (web->color >= web2->color + nregs2
		  || web2->color >= web->color + nregs)
		continue;
	      old_colors[web2->id] = web2->color + 1;
	      web2->color = -1;
	      remove_list (web2->dlink, &WEBS(COLORED));
	      web2->type = SELECT;
	      /* Allow webs to be spilled.  */
	      if (web2->spill_temp == 0 || web2->spill_temp == 2)
		web2->was_spilled = 1;
	      colorize_one_web (web2, 1);
	      if (web2->type == SPILLED)
		cost += web2->spill_cost;
	    }
	}
      /* The actual cost may be smaller than the guessed one, because
	 partial conflicts could result in some conflicting webs getting
	 a color, where we assumed it must be spilled.  See the comment
         above what happens, when wide webs are involved, and why in that
         case there might actually be some webs spilled although thought to
         be colorable.  */
      if (cost > cost_neighbors[newcol]
	  && nregs == 1 && !TEST_HARD_REG_BIT (wide_seen, newcol))
	abort ();
      /* But if the new spill-cost is higher than our own, then really loose.
	 Respill us and recolor neighbors as before.  */
      if (cost > web->spill_cost)
	{
	  ra_debug_msg (DUMP_COLORIZE,
		     "reset coloring of web %d, too expensive\n", web->id);
	  remove_list (web->dlink, &WEBS(COLORED));
	  web->color = -1;
	  put_web (web, SPILLED);
	  for (wl = web->conflict_list; wl; wl = wl->next)
	    {
	      struct web *web2 = alias (wl->t);
	      if (old_colors[web2->id])
		{
		  if (web2->type == SPILLED)
		    {
		      remove_list (web2->dlink, &WEBS(SPILLED));
		      web2->color = old_colors[web2->id] - 1;
		      put_web (web2, COLORED);
		    }
		  else if (web2->type == COLORED)
		    web2->color = old_colors[web2->id] - 1;
		  else if (web2->type == SELECT)
		    /* This means, that WEB2 once was a part of a coalesced
		       web, which got spilled in the above colorize_one_web()
		       call, and whose parts then got split and put back
		       onto the SELECT stack.  As the cause for that splitting
		       (the coloring of WEB) was worthless, we should again
		       coalesce the parts, as they were before.  For now we
		       simply leave them SELECTed, for our caller to take
		       care.  */
		    ;
		  else
		    abort ();
		}
	    }
	}
      free (old_colors);
    }
  free (min_color);
  free (cost_neighbors);
}

/* This ensures that all conflicts of coalesced webs are seen from
   the webs coalesced into.  combine() only adds the conflicts which
   at the time of combining were not already SELECTed or COALESCED
   to not destroy num_conflicts.  Here we add all remaining conflicts
   and thereby destroy num_conflicts.  This should be used when num_conflicts
   isn't used anymore, e.g. on a completely colored graph.  */

static void
insert_coalesced_conflicts (void)
{
  struct dlist *d;
  for (d = WEBS(COALESCED); 0 && d; d = d->next)
    {
      struct web *web = DLIST_WEB (d);
      struct web *aweb = alias (web);
      struct conflict_link *wl;
      for (wl = web->conflict_list; wl; wl = wl->next)
	{
	  struct web *tweb = aweb;
	  int i;
	  int nregs = 1 + web->add_hardregs;
	  if (aweb->type == PRECOLORED)
	    nregs = hard_regno_nregs[aweb->color][GET_MODE (web->orig_x)];
	  for (i = 0; i < nregs; i++)
	    {
	      if (aweb->type == PRECOLORED)
		tweb = hardreg2web[i + aweb->color];
	      /* There might be some conflict edges laying around
		 where the usable_regs don't intersect.  This can happen
		 when first some webs were coalesced and conflicts
		 propagated, then some combining narrowed usable_regs and
		 further coalescing ignored those conflicts.  Now there are
		 some edges to COALESCED webs but not to it's alias.
		 So abort only when they really should conflict.  */
	      if ((!(tweb->type == PRECOLORED
		     || TEST_BIT (sup_igraph, tweb->id * num_webs + wl->t->id))
		   || !(wl->t->type == PRECOLORED
		        || TEST_BIT (sup_igraph,
				     wl->t->id * num_webs + tweb->id)))
		  && hard_regs_intersect_p (&tweb->usable_regs,
					    &wl->t->usable_regs))
		abort ();
	      /*if (wl->sub == NULL)
		record_conflict (tweb, wl->t);
	      else
		{
		  struct sub_conflict *sl;
		  for (sl = wl->sub; sl; sl = sl->next)
		    record_conflict (tweb, sl->t);
		}*/
	      if (aweb->type != PRECOLORED)
		break;
	    }
	}
    }
}

/* A function suitable to pass to qsort().  Compare the spill costs
   of webs W1 and W2.  When used by qsort, this would order webs with
   largest cost first.  */

static int
comp_webs_maxcost (const void *w1, const void *w2)
{
  struct web *web1 = *(struct web **)w1;
  struct web *web2 = *(struct web **)w2;
  if (web1->spill_cost > web2->spill_cost)
    return -1;
  else if (web1->spill_cost < web2->spill_cost)
    return 1;
  else
    return 0;
}

/* This tries to recolor all spilled webs.  See try_recolor_web()
   how this is done.  This just calls it for each spilled web.  */

static void
recolor_spills (void)
{
  unsigned int i, num;
  struct web **order2web;
  num = num_webs - num_subwebs;
  order2web = xmalloc (num * sizeof (order2web[0]));
  for (i = 0; i < num; i++)
    {
      order2web[i] = id2web[i];
      /* If we aren't breaking aliases, combine() wasn't merging the
         spill_costs.  So do that here to have sane measures.  */
      if (!flag_ra_merge_spill_costs && id2web[i]->type == COALESCED)
	alias (id2web[i])->spill_cost += id2web[i]->spill_cost;
    }
  qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
  insert_coalesced_conflicts ();
  dump_graph_cost (DUMP_COSTS, "before spill-recolor");
  for (i = 0; i < num; i++)
    {
      struct web *web = order2web[i];
      if (web->type == SPILLED)
	try_recolor_web (web);
    }
  /* It might have been decided in try_recolor_web() (in colorize_one_web())
     that a coalesced web should be spilled, so it was put on the
     select stack.  Those webs need recoloring again, and all remaining
     coalesced webs might need their color updated, so simply call
     assign_colors() again.  */
  assign_colors ();
  free (order2web);
}

/* This checks the current color assignment for obvious errors,
   like two conflicting webs overlapping in colors, or the used colors
   not being in usable regs.  */

static void
check_colors (void)
{
  unsigned int i;
  for (i = 0; i < num_webs - num_subwebs; i++)
    {
      struct web *web = id2web[i];
      struct web *aweb = alias (web);
      struct conflict_link *wl;
      int nregs, c;
      if (aweb->type == SPILLED || web->regno >= max_normal_pseudo)
	continue;
      else if (aweb->type == COLORED)
	nregs = hard_regno_nregs[aweb->color][GET_MODE (web->orig_x)];
      else if (aweb->type == PRECOLORED)
	nregs = 1;
      else
	abort ();
      /* The color must be valid for the original usable_regs.  */
      for (c = 0; c < nregs; c++)
	if (!TEST_HARD_REG_BIT (web->usable_regs, aweb->color + c))
	  abort ();
      /* Search the original (pre-coalesce) conflict list.  In the current
	 one some imprecise conflicts may be noted (due to combine() or
	 insert_coalesced_conflicts() relocating partial conflicts) making
	 it look like some wide webs are in conflict and having the same
	 color.  */
      wl = (web->have_orig_conflicts ? web->orig_conflict_list
	    : web->conflict_list);
      for (; wl; wl = wl->next)
	if (wl->t->regno >= max_normal_pseudo)
	  continue;
	else if (!wl->sub)
	  {
	    struct web *web2 = alias (wl->t);
	    int nregs2;
	    if (web2->type == COLORED)
	      nregs2 = hard_regno_nregs[web2->color][GET_MODE (web2->orig_x)];
	    else if (web2->type == PRECOLORED)
	      nregs2 = 1;
	    else
	      continue;
	    if (aweb->color >= web2->color + nregs2
	        || web2->color >= aweb->color + nregs)
	      continue;
	    abort ();
	  }
	else
	  {
	    struct sub_conflict *sl;
	    int scol = aweb->color;
	    int tcol = alias (wl->t)->color;
	    if (alias (wl->t)->type == SPILLED)
	      continue;
	    for (sl = wl->sub; sl; sl = sl->next)
	      {
		int ssize = hard_regno_nregs[scol][GET_MODE (sl->s->orig_x)];
		int tsize = hard_regno_nregs[tcol][GET_MODE (sl->t->orig_x)];
		int sofs = 0, tofs = 0;
	        if (SUBWEB_P (sl->t)
		    && GET_MODE_SIZE (GET_MODE (sl->t->orig_x)) >= UNITS_PER_WORD)
		  tofs = (SUBREG_BYTE (sl->t->orig_x) / UNITS_PER_WORD);
	        if (SUBWEB_P (sl->s)
		    && GET_MODE_SIZE (GET_MODE (sl->s->orig_x))
		       >= UNITS_PER_WORD)
		  sofs = (SUBREG_BYTE (sl->s->orig_x) / UNITS_PER_WORD);
		if ((tcol + tofs >= scol + sofs + ssize)
		    || (scol + sofs >= tcol + tofs + tsize))
		  continue;
		abort ();
	      }
	  }
    }
}

/* WEB was a coalesced web.  Make it unaliased again, and put it
   back onto SELECT stack.  */

static void
unalias_web (struct web *web)
{
  web->alias = NULL;
  web->is_coalesced = 0;
  web->color = -1;
  /* Well, initially everything was spilled, so it isn't incorrect,
     that also the individual parts can be spilled.
     XXX this isn't entirely correct, as we also relaxed the
     spill_temp flag in combine(), which might have made components
     spill, although they were a short or spilltemp web.  */
  web->was_spilled = 1;
  remove_list (web->dlink, &WEBS(COALESCED));
  /* Spilltemps must be colored right now (i.e. as early as possible),
     other webs can be deferred to the end (the code building the
     stack assumed that in this stage only one web was colored).  */
  if (web->spill_temp && web->spill_temp != 2)
    put_web (web, SELECT);
  else
    put_web_at_end (web, SELECT);
}

/* WEB is a _target_ for coalescing which got spilled.
   Break all aliases to WEB, and restore some of its member to the state
   they were before coalescing.  Due to the suboptimal structure of
   the interference graph we need to go through all coalesced webs.
   Somewhen we'll change this to be more sane.  */

static void
break_aliases_to_web (struct web *web)
{
  struct dlist *d, *d_next;
  if (web->type != SPILLED)
    abort ();
  for (d = WEBS(COALESCED); d; d = d_next)
    {
      struct web *other = DLIST_WEB (d);
      d_next = d->next;
      /* Beware: Don't use alias() here.  We really want to check only
	 one level of aliasing, i.e. only break up webs directly
	 aliased to WEB, not also those aliased through other webs.  */
      if (other->alias == web)
	{
	  unalias_web (other);
	  ra_debug_msg (DUMP_COLORIZE, " %d", other->id);
	}
    }
  web->spill_temp = web->orig_spill_temp;
  web->spill_cost = web->orig_spill_cost;
  /* Beware: The following possibly widens usable_regs again.  While
     it was narrower there might have been some conflicts added which got
     ignored because of non-intersecting hardregsets.  All those conflicts
     would now matter again.  Fortunately we only add conflicts when
     coalescing, which is also the time of narrowing.  And we remove all
     those added conflicts again now that we unalias this web.
     Therefore this is safe to do.  */
  COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
  web->is_coalesced = 0;
  web->num_aliased = 0;
  web->was_spilled = 1;
  /* Reset is_coalesced flag for webs which itself are target of coalescing.
     It was cleared above if it was coalesced to WEB.  */
  for (d = WEBS(COALESCED); d; d = d->next)
    DLIST_WEB (d)->alias->is_coalesced = 1;
}

/* WEB is a web coalesced into a precolored one.  Break that alias,
   making WEB SELECTed again.  Also restores the conflicts which resulted
   from initially coalescing both.  */

static void
break_precolored_alias (struct web *web)
{
  struct web *pre = web->alias;
  struct conflict_link *wl;
  unsigned int c = pre->color;
  unsigned int nregs = hard_regno_nregs[c][GET_MODE (web->orig_x)];
  if (pre->type != PRECOLORED)
    abort ();
  unalias_web (web);
  /* Now we need to look at each conflict X of WEB, if it conflicts
     with [PRE, PRE+nregs), and remove such conflicts, of X has not other
     conflicts, which are coalesced into those precolored webs.  */
  for (wl = web->conflict_list; wl; wl = wl->next)
    {
      struct web *x = wl->t;
      struct web *y;
      unsigned int i;
      struct conflict_link *wl2;
      struct conflict_link **pcl;
      HARD_REG_SET regs;
      if (!x->have_orig_conflicts)
	continue;
      /* First look at which colors can not go away, due to other coalesces
	 still existing.  */
      CLEAR_HARD_REG_SET (regs);
      for (i = 0; i < nregs; i++)
	SET_HARD_REG_BIT (regs, c + i);
      for (wl2 = x->conflict_list; wl2; wl2 = wl2->next)
	if (wl2->t->type == COALESCED && alias (wl2->t)->type == PRECOLORED)
	  CLEAR_HARD_REG_BIT (regs, alias (wl2->t)->color);
      /* Now also remove the colors of those conflicts which already
	 were there before coalescing at all.  */
      for (wl2 = x->orig_conflict_list; wl2; wl2 = wl2->next)
	if (wl2->t->type == PRECOLORED)
	  CLEAR_HARD_REG_BIT (regs, wl2->t->color);
      /* The colors now still set are those for which WEB was the last
	 cause, i.e. those which can be removed.  */
      y = NULL;
      for (i = 0; i < nregs; i++)
	if (TEST_HARD_REG_BIT (regs, c + i))
	  {
	    struct web *sub;
	    y = hardreg2web[c + i];
	    RESET_BIT (sup_igraph, x->id * num_webs + y->id);
	    RESET_BIT (sup_igraph, y->id * num_webs + x->id);
	    RESET_BIT (igraph, igraph_index (x->id, y->id));
	    for (sub = x->subreg_next; sub; sub = sub->subreg_next)
	      RESET_BIT (igraph, igraph_index (sub->id, y->id));
	  }
      if (!y)
	continue;
      pcl = &(x->conflict_list);
      while (*pcl)
	{
	  struct web *y = (*pcl)->t;
	  if (y->type != PRECOLORED || !TEST_HARD_REG_BIT (regs, y->color))
	    pcl = &((*pcl)->next);
	  else
	    *pcl = (*pcl)->next;
	}
    }
}

/* WEB is a spilled web which was target for coalescing.
   Delete all interference edges which were added due to that coalescing,
   and break up the coalescing.  */

static void
restore_conflicts_from_coalesce (struct web *web)
{
  struct conflict_link **pcl;
  struct conflict_link *wl;
  pcl = &(web->conflict_list);
  /* No original conflict list means no conflict was added at all
     after building the graph.  So neither we nor any neighbors have
     conflicts due to this coalescing.  */
  if (!web->have_orig_conflicts)
    return;
  while (*pcl)
    {
      struct web *other = (*pcl)->t;
      for (wl = web->orig_conflict_list; wl; wl = wl->next)
	if (wl->t == other)
	  break;
      if (wl)
	{
	  /* We found this conflict also in the original list, so this
	     was no new conflict.  */
	  pcl = &((*pcl)->next);
	}
      else
	{
	  /* This is a new conflict, so delete it from us and
	     the neighbor.  */
	  struct conflict_link **opcl;
	  struct conflict_link *owl;
	  struct sub_conflict *sl;
	  wl = *pcl;
	  *pcl = wl->next;
	  if (!other->have_orig_conflicts && other->type != PRECOLORED)
	    abort ();
	  for (owl = other->orig_conflict_list; owl; owl = owl->next)
	    if (owl->t == web)
	      break;
	  if (owl)
	    abort ();
	  opcl = &(other->conflict_list);
	  while (*opcl)
	    {
	      if ((*opcl)->t == web)
		{
		  owl = *opcl;
		  *opcl = owl->next;
		  break;
		}
	      else
		{
		  opcl = &((*opcl)->next);
		}
	    }
	  if (!owl && other->type != PRECOLORED)
	    abort ();
	  /* wl and owl contain the edge data to be deleted.  */
	  RESET_BIT (sup_igraph, web->id * num_webs + other->id);
	  RESET_BIT (sup_igraph, other->id * num_webs + web->id);
	  RESET_BIT (igraph, igraph_index (web->id, other->id));
	  for (sl = wl->sub; sl; sl = sl->next)
	    RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
	  if (other->type != PRECOLORED)
	    {
	      for (sl = owl->sub; sl; sl = sl->next)
		RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
	    }
	}
    }

  /* We must restore usable_regs because record_conflict will use it.  */
  COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
  /* We might have deleted some conflicts above, which really are still
     there (diamond pattern coalescing).  This is because we don't reference
     count interference edges but some of them were the result of different
     coalesces.  */
  for (wl = web->conflict_list; wl; wl = wl->next)
    if (wl->t->type == COALESCED)
      {
	struct web *tweb;
	for (tweb = wl->t->alias; tweb; tweb = tweb->alias)
	  {
	    if (wl->sub == NULL)
	      record_conflict (web, tweb);
	    else
	      {
		struct sub_conflict *sl;
		for (sl = wl->sub; sl; sl = sl->next)
		  {
		    struct web *sweb = NULL;
		    if (SUBWEB_P (sl->t))
		      sweb = find_subweb (tweb, sl->t->orig_x);
		    if (!sweb)
		      sweb = tweb;
		    record_conflict (sl->s, sweb);
		  }
	      }
	    if (tweb->type != COALESCED)
	      break;
	  }
      }
}

/* Repeatedly break aliases for spilled webs, which were target for
   coalescing, and recolorize the resulting parts.  Do this as long as
   there are any spilled coalesce targets.  */

static void
break_coalesced_spills (void)
{
  int changed = 0;
  while (1)
    {
      struct dlist *d;
      struct web *web;
      for (d = WEBS(SPILLED); d; d = d->next)
	if (DLIST_WEB (d)->is_coalesced)
	  break;
      if (!d)
	break;
      changed = 1;
      web = DLIST_WEB (d);
      ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
      restore_conflicts_from_coalesce (web);
      break_aliases_to_web (web);
      /* WEB was a spilled web and isn't anymore.  Everything coalesced
	 to WEB is now SELECTed and might potentially get a color.
	 If those other webs were itself targets of coalescing it might be
	 that there are still some conflicts from aliased webs missing,
	 because they were added in combine() right into the now
	 SELECTed web.  So we need to add those missing conflicts here.  */
      insert_coalesced_conflicts ();
      ra_debug_msg (DUMP_COLORIZE, "\n");
      remove_list (d, &WEBS(SPILLED));
      put_web (web, SELECT);
      web->color = -1;
      while (WEBS(SELECT))
	{
	  d = pop_list (&WEBS(SELECT));
	  colorize_one_web (DLIST_WEB (d), 1);
	}
    }
  if (changed)
    {
      struct dlist *d;
      for (d = WEBS(COALESCED); d; d = d->next)
	{
	  struct web *a = alias (DLIST_WEB (d));
	  DLIST_WEB (d)->color = a->color;
	}
    }
  dump_graph_cost (DUMP_COSTS, "after alias-breaking");
}

/* A structure for fast hashing of a pair of webs.
   Used to cumulate savings (from removing copy insns) for coalesced webs.
   All the pairs are also put into a single linked list.  */
struct web_pair
{
  struct web_pair *next_hash;
  struct web_pair *next_list;
  struct web *smaller;
  struct web *larger;
  unsigned int conflicts;
  unsigned HOST_WIDE_INT cost;
};

/* The actual hash table.  */
#define WEB_PAIR_HASH_SIZE 8192
static struct web_pair *web_pair_hash[WEB_PAIR_HASH_SIZE];
static struct web_pair *web_pair_list;
static unsigned int num_web_pairs;

/* Clear the hash table of web pairs.  */

static void
init_web_pairs (void)
{
  memset (web_pair_hash, 0, sizeof web_pair_hash);
  num_web_pairs = 0;
  web_pair_list = NULL;
}

/* Given two webs connected by a move with cost COST which together
   have CONFLICTS conflicts, add that pair to the hash table, or if
   already in, cumulate the costs and conflict number.  */

static void
add_web_pair_cost (struct web *web1, struct web *web2,
		   unsigned HOST_WIDE_INT cost, unsigned int conflicts)
{
  unsigned int hash;
  struct web_pair *p;
  if (web1->id > web2->id)
    {
      struct web *h = web1;
      web1 = web2;
      web2 = h;
    }
  hash = (web1->id * num_webs + web2->id) % WEB_PAIR_HASH_SIZE;
  for (p = web_pair_hash[hash]; p; p = p->next_hash)
    if (p->smaller == web1 && p->larger == web2)
      {
	p->cost += cost;
	p->conflicts += conflicts;
	return;
      }
  p = ra_alloc (sizeof *p);
  p->next_hash = web_pair_hash[hash];
  p->next_list = web_pair_list;
  p->smaller = web1;
  p->larger = web2;
  p->conflicts = conflicts;
  p->cost = cost;
  web_pair_hash[hash] = p;
  web_pair_list = p;
  num_web_pairs++;
}

/* Suitable to be passed to qsort().  Sort web pairs so, that those
   with more conflicts and higher cost (which actually is a saving
   when the moves are removed) come first.  */

static int
comp_web_pairs (const void *w1, const void *w2)
{
  struct web_pair *p1 = *(struct web_pair **)w1;
  struct web_pair *p2 = *(struct web_pair **)w2;
  if (p1->conflicts > p2->conflicts)
    return -1;
  else if (p1->conflicts < p2->conflicts)
    return 1;
  else if (p1->cost > p2->cost)
    return -1;
  else if (p1->cost < p2->cost)
    return 1;
  else
    return 0;
}

/* Given the list of web pairs, begin to combine them from the one
   with the most savings.  */

static void
sort_and_combine_web_pairs (int for_move)
{
  unsigned int i;
  struct web_pair **sorted;
  struct web_pair *p;
  if (!num_web_pairs)
    return;
  sorted = xmalloc (num_web_pairs * sizeof (sorted[0]));
  for (p = web_pair_list, i = 0; p; p = p->next_list)
    sorted[i++] = p;
  if (i != num_web_pairs)
    abort ();
  qsort (sorted, num_web_pairs, sizeof (sorted[0]), comp_web_pairs);

  /* After combining one pair, we actually should adjust the savings
     of the other pairs, if they are connected to one of the just coalesced
     pair.  Later.  */
  for (i = 0; i < num_web_pairs; i++)
    {
      struct web *w1, *w2;
      p = sorted[i];
      w1 = alias (p->smaller);
      w2 = alias (p->larger);
      if (!for_move && (w1->type == PRECOLORED || w2->type == PRECOLORED))
	continue;
      else if (w2->type == PRECOLORED)
	{
	  struct web *h = w1;
	  w1 = w2;
	  w2 = h;
	}
      if (w1 != w2
	  && !TEST_BIT (sup_igraph, w1->id * num_webs + w2->id)
	  && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id)
	  && w2->type != PRECOLORED
	  && hard_regs_intersect_p (&w1->usable_regs, &w2->usable_regs))
	  {
	    if (w1->type != PRECOLORED
		|| (w1->type == PRECOLORED && ok (w2, w1)))
	      combine (w1, w2);
	    else if (w1->type == PRECOLORED)
	      SET_HARD_REG_BIT (w2->prefer_colors, w1->color);
	  }
    }
  free (sorted);
}

/* Returns nonzero if source/target reg classes are ok for coalesce.  */

static int
ok_class (struct web *target, struct web *source)
{
  /* Don't coalesce if preferred classes are different and at least one
     of them has a size of 1. This was preventing things such as the
     branch on count transformation (i.e. DoLoop) since the target, which
     prefers the CTR, was being coalesced with a source which preferred
     GENERAL_REGS. If only one web has a preferred class with 1 free reg
     then set it as the preferred color of the other web.   */
  enum reg_class t_class, s_class;
  t_class = reg_preferred_class (target->regno);
  s_class = reg_preferred_class (source->regno);
  if (t_class != s_class)
    {
      if (num_free_regs[t_class] == 1)
	{
	  if (num_free_regs[s_class] != 1)
	    SET_HARD_REG_BIT (source->prefer_colors,
			      single_reg_in_regclass[t_class]);
	  return 0;
	}
      else if (num_free_regs[s_class] == 1)
	{
	    SET_HARD_REG_BIT (target->prefer_colors,
			      single_reg_in_regclass[s_class]);
	  return 0;
	}
    }
  return 1;
}

/* Greedily coalesce all moves possible.  Begin with the web pair
   giving the most saving if coalesced.  */

static void
aggressive_coalesce (void)
{
  struct dlist *d;
  struct move *m;
  init_web_pairs ();
  while ((d = pop_list (&mv_worklist)) != NULL)
    if ((m = DLIST_MOVE (d)))
      {
	struct web *s = alias (m->source_web);
	struct web *t = alias (m->target_web);
	if (t->type == PRECOLORED)
	  {
	    struct web *h = s;
	    s = t;
	    t = h;
	  }
	if (s != t
	    && t->type != PRECOLORED
	    && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
	    && !TEST_BIT (sup_igraph, t->id * num_webs + s->id)
	    && ok_class (t, s))
	  {
	    if ((s->type == PRECOLORED && ok (t, s))
		|| s->type != PRECOLORED)
	      {
	        put_move (m, MV_COALESCED);
		add_web_pair_cost (s, t, BLOCK_FOR_INSN (m->insn)->frequency,
				   0);
	      }
	    else if (s->type == PRECOLORED)
	      /* It is !ok(t, s).  But later when coloring the graph it might
		 be possible to take that color.  So we remember the preferred
		 color to try that first.  */
	      {
		put_move (m, CONSTRAINED);
		SET_HARD_REG_BIT (t->prefer_colors, s->color);
	      }
	  }
	else
	  {
	    put_move (m, CONSTRAINED);
	  }
      }
  sort_and_combine_web_pairs (1);
}

/* This is the difference between optimistic coalescing and
   optimistic coalescing+.  Extended coalesce tries to coalesce also
   non-conflicting nodes, not related by a move.  The criteria here is,
   the one web must be a source, the other a destination of the same insn.
   This actually makes sense, as (because they are in the same insn) they
   share many of their neighbors, and if they are coalesced, reduce the
   number of conflicts of those neighbors by one.  For this we sort the
   candidate pairs again according to savings (and this time also conflict
   number).

   This is also a comparatively slow operation, as we need to go through
   all insns, and for each insn, through all defs and uses.  */

static void
extended_coalesce_2 (void)
{
  rtx insn;
  struct ra_insn_info info;
  unsigned int n;
  init_web_pairs ();
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    if (INSN_P (insn) && (info = insn_df[INSN_UID (insn)]).num_defs)
      for (n = 0; n < info.num_defs; n++)
	{
	  struct web *dest = def2web[DF_REF_ID (info.defs[n])];
	  dest = alias (find_web_for_subweb (dest));
	  if (dest->type != PRECOLORED && dest->regno < max_normal_pseudo)
	    {
	      unsigned int n2;
	      for (n2 = 0; n2 < info.num_uses; n2++)
		{
		  struct web *source = use2web[DF_REF_ID (info.uses[n2])];
		  source = alias (find_web_for_subweb (source));
		  if (source->type != PRECOLORED
		      && source != dest
		      && source->regno < max_normal_pseudo
		      /* Coalesced webs end up using the same REG rtx in
			 emit_colors().  So we can only coalesce something
			 of equal modes.  */
		      && GET_MODE (source->orig_x) == GET_MODE (dest->orig_x)
		      && !TEST_BIT (sup_igraph,
				    dest->id * num_webs + source->id)
		      && !TEST_BIT (sup_igraph,
				    source->id * num_webs + dest->id)
		      && ok_class (dest, source)
		      && hard_regs_intersect_p (&source->usable_regs,
						&dest->usable_regs))
		    add_web_pair_cost (dest, source,
				       BLOCK_FOR_INSN (insn)->frequency,
				       dest->num_conflicts
				       + source->num_conflicts);
		}
	    }
	}
  sort_and_combine_web_pairs (0);
}

/* Check if we forgot to coalesce some moves.  */

static void
check_uncoalesced_moves (void)
{
  struct move_list *ml;
  struct move *m;
  for (ml = wl_moves; ml; ml = ml->next)
    if ((m = ml->move))
      {
	struct web *s = alias (m->source_web);
	struct web *t = alias (m->target_web);
	if (t->type == PRECOLORED)
	  {
	    struct web *h = s;
	    s = t;
	    t = h;
	  }
	if (s != t
	    && m->type != CONSTRAINED
	    /* Following can happen when a move was coalesced, but later
	       broken up again.  Then s!=t, but m is still MV_COALESCED.  */
	    && m->type != MV_COALESCED
	    && t->type != PRECOLORED
	    && ((s->type == PRECOLORED && ok (t, s))
		|| s->type != PRECOLORED)
	    && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
	    && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
	  abort ();
      }
}

/* The toplevel function in this file.  Precondition is, that
   the interference graph is built completely by ra-build.c.  This
   produces a list of spilled, colored and coalesced nodes.  */

void
ra_colorize_graph (struct df *df)
{
  if (dump_file)
    dump_igraph (df);
  build_worklists (df);

  /* With optimistic coalescing we coalesce everything we can.  */
  if (flag_ra_optimistic_coalescing)
    {
      aggressive_coalesce ();
      extended_coalesce_2 ();
    }

  /* Now build the select stack.  */
  do
    {
      simplify ();
      if (mv_worklist)
	coalesce ();
      else if (WEBS(FREEZE))
	freeze ();
      else if (WEBS(SPILL))
	select_spill ();
    }
  while (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_FAT) || WEBS(SIMPLIFY_SPILL)
	 || mv_worklist || WEBS(FREEZE) || WEBS(SPILL));
  if (flag_ra_optimistic_coalescing)
    check_uncoalesced_moves ();

  /* Actually colorize the webs from the select stack.  */
  assign_colors ();
  check_colors ();
  dump_graph_cost (DUMP_COSTS, "initially");
  if (flag_ra_break_aliases)
    break_coalesced_spills ();
  check_colors ();

  /* And try to improve the cost by recoloring spilled webs.  */
  recolor_spills ();
  dump_graph_cost (DUMP_COSTS, "after spill-recolor");
  check_colors ();
}

/* Initialize this module.  */

void ra_colorize_init (void)
{
  /* FIXME: Choose spill heuristic for platform if we have one */
  spill_heuristic = default_spill_heuristic;
}

/* Free all memory.  (Note that we don't need to free any per pass
   memory).  */

void
ra_colorize_free_all (void)
{
  struct dlist *d;
  while ((d = pop_list (&WEBS(FREE))) != NULL)
    put_web (DLIST_WEB (d), INITIAL);
  while ((d = pop_list (&WEBS(INITIAL))) != NULL)
    {
      struct web *web = DLIST_WEB (d);
      struct web *wnext;
      web->orig_conflict_list = NULL;
      web->conflict_list = NULL;
      for (web = web->subreg_next; web; web = wnext)
	{
	  wnext = web->subreg_next;
	  free (web);
	}
      free (DLIST_WEB (d));
    }
}

/*
vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
*/