gcc/gcc/ra.c

/* 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 "reload.h"
#include "integrate.h"
#include "function.h"
#include "regs.h"
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "df.h"
#include "expr.h"
#include "output.h"
#include "toplev.h"
#include "flags.h"
#include "ra.h"

/* This is the toplevel file of a graph coloring register allocator.
   It is able to act like a George & Appel allocator, i.e. with iterative
   coalescing plus spill coalescing/propagation.
   And it can act as a traditional Briggs allocator, although with
   optimistic coalescing.  Additionally it has a custom pass, which
   tries to reduce the overall cost of the colored graph.

   We support two modes of spilling: spill-everywhere, which is extremely
   fast, and interference region spilling, which reduces spill code to a
   large extent, but is slower.

   Helpful documents:

   Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
   coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
   428-455.

   Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
   minimization via interference region spilling. In Proc. ACM SIGPLAN '97
   Conf. on Prog. Language Design and Implementation. ACM, 287-295.

   George, L., Appel, A.W. 1996.  Iterated register coalescing.
   ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.

*/

/* This file contains the main entry point (reg_alloc), some helper routines
   used by more than one file of the register allocator, and the toplevel
   driver procedure (one_pass).  */

/* Things, one might do somewhen:

   * Lattice based rematerialization
   * create definitions of ever-life regs at the beginning of
     the insn chain
   * insert loads as soon, stores as late as possile
   * insert spill insns as outward as possible (either looptree, or LCM)
   * reuse stack-slots
   * delete coalesced insns.  Partly done.  The rest can only go, when we get
     rid of reload.
   * don't destroy coalescing information completely when spilling
   * use the constraints from asms
  */

static struct obstack ra_obstack;
static void create_insn_info PARAMS ((struct df *));
static void free_insn_info PARAMS ((void));
static void alloc_mem PARAMS ((struct df *));
static void free_mem PARAMS ((struct df *));
static void free_all_mem PARAMS ((struct df *df));
static int one_pass PARAMS ((struct df *, int));
static void check_df PARAMS ((struct df *));
static void init_ra PARAMS ((void));

void reg_alloc PARAMS ((void));

/* These global variables are "internal" to the register allocator.
   They are all documented at their declarations in ra.h.  */

/* Somewhen we want to get rid of one of those sbitmaps.
   (for now I need the sup_igraph to note if there is any conflict between
   parts of webs at all.  I can't use igraph for this, as there only the real
   conflicts are noted.)  This is only used to prevent coalescing two
   conflicting webs, were only parts of them are in conflict.  */
sbitmap igraph;
sbitmap sup_igraph;

/* Note the insns not inserted by the allocator, where we detected any
   deaths of pseudos.  It is used to detect closeness of defs and uses.
   In the first pass this is empty (we could initialize it from REG_DEAD
   notes), in the other passes it is left from the pass before.  */
sbitmap insns_with_deaths;
int death_insns_max_uid;

struct web_part *web_parts;

unsigned int num_webs;
unsigned int num_subwebs;
unsigned int num_allwebs;
struct web **id2web;
struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
struct web **def2web;
struct web **use2web;
struct move_list *wl_moves;
int ra_max_regno;
short *ra_reg_renumber;
struct df *df;
bitmap *live_at_end;
int ra_pass;
unsigned int max_normal_pseudo;
int an_unusable_color;

/* The different lists on which a web can be (based on the type).  */
struct dlist *web_lists[(int) LAST_NODE_TYPE];

unsigned int last_def_id;
unsigned int last_use_id;
unsigned int last_num_webs;
int last_max_uid;
sbitmap last_check_uses;
unsigned int remember_conflicts;

int orig_max_uid;

HARD_REG_SET never_use_colors;
HARD_REG_SET usable_regs[N_REG_CLASSES];
unsigned int num_free_regs[N_REG_CLASSES];
HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
unsigned char byte2bitcount[256];

unsigned int debug_new_regalloc = -1;
int flag_ra_biased = 0;
int flag_ra_improved_spilling = 0;
int flag_ra_ir_spilling = 0;
int flag_ra_optimistic_coalescing = 0;
int flag_ra_break_aliases = 0;
int flag_ra_merge_spill_costs = 0;
int flag_ra_spill_every_use = 0;
int flag_ra_dump_notes = 0;

/* Fast allocation of small objects, which live until the allocator
   is done.  Allocate an object of SIZE bytes.  */

void *
ra_alloc (size)
     size_t size;
{
  return obstack_alloc (&ra_obstack, size);
}

/* Like ra_alloc(), but clear the returned memory.  */

void *
ra_calloc (size)
     size_t size;
{
  void *p = obstack_alloc (&ra_obstack, size);
  memset (p, 0, size);
  return p;
}

/* Returns the number of hardregs in HARD_REG_SET RS.  */

int
hard_regs_count (rs)
     HARD_REG_SET rs;
{
  int count = 0;
#ifdef HARD_REG_SET
  while (rs)
    {
      unsigned char byte = rs & 0xFF;
      rs >>= 8;
      /* Avoid memory access, if nothing is set.  */
      if (byte)
        count += byte2bitcount[byte];
    }
#else
  unsigned int ofs;
  for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
    {
      HARD_REG_ELT_TYPE elt = rs[ofs];
      while (elt)
	{
	  unsigned char byte = elt & 0xFF;
	  elt >>= 8;
	  if (byte)
	    count += byte2bitcount[byte];
	}
    }
#endif
  return count;
}

/* Basically like emit_move_insn (i.e. validifies constants and such),
   but also handle MODE_CC moves (but then the operands must already
   be basically valid.  */

rtx
ra_emit_move_insn (x, y)
     rtx x, y;
{
  enum machine_mode mode = GET_MODE (x);
  if (GET_MODE_CLASS (mode) == MODE_CC)
    return emit_insn (gen_move_insn (x, y));
  else
    return emit_move_insn (x, y);
}

int insn_df_max_uid;
struct ra_insn_info *insn_df;
static struct ref **refs_for_insn_df;

/* Create the insn_df structure for each insn to have fast access to
   all valid defs and uses in an insn.  */

static void
create_insn_info (df)
     struct df *df;
{
  rtx insn;
  struct ref **act_refs;
  insn_df_max_uid = get_max_uid ();
  insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
  refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
  act_refs = refs_for_insn_df;
  /* We create those things backwards to mimic the order in which
     the insns are visited in rewrite_program2() and live_in().  */
  for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
    {
      int uid = INSN_UID (insn);
      unsigned int n;
      struct df_link *link;
      if (!INSN_P (insn))
	continue;
      for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
        if (link->ref
	    && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
		|| !TEST_HARD_REG_BIT (never_use_colors,
				       DF_REF_REGNO (link->ref))))
	  {
	    if (n == 0)
	      insn_df[uid].defs = act_refs;
	    insn_df[uid].defs[n++] = link->ref;
	  }
      act_refs += n;
      insn_df[uid].num_defs = n;
      for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
        if (link->ref
	    && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
		|| !TEST_HARD_REG_BIT (never_use_colors,
				       DF_REF_REGNO (link->ref))))
	  {
	    if (n == 0)
	      insn_df[uid].uses = act_refs;
	    insn_df[uid].uses[n++] = link->ref;
	  }
      act_refs += n;
      insn_df[uid].num_uses = n;
    }
  if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
    abort ();
}

/* Free the insn_df structures.  */

static void
free_insn_info ()
{
  free (refs_for_insn_df);
  refs_for_insn_df = NULL;
  free (insn_df);
  insn_df = NULL;
  insn_df_max_uid = 0;
}

/* Search WEB for a subweb, which represents REG.  REG needs to
   be a SUBREG, and the inner reg of it needs to be the one which is
   represented by WEB.  Returns the matching subweb or NULL.  */

struct web *
find_subweb (web, reg)
     struct web *web;
     rtx reg;
{
  struct web *w;
  if (GET_CODE (reg) != SUBREG)
    abort ();
  for (w = web->subreg_next; w; w = w->subreg_next)
    if (GET_MODE (w->orig_x) == GET_MODE (reg)
	&& SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
      return w;
  return NULL;
}

/* Similar to find_subweb(), but matches according to SIZE_WORD,
   a collection of the needed size and offset (in bytes).  */

struct web *
find_subweb_2 (web, size_word)
     struct web *web;
     unsigned int size_word;
{
  struct web *w = web;
  if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
    /* size_word == size means BYTE_BEGIN(size_word) == 0.  */
    return web;
  for (w = web->subreg_next; w; w = w->subreg_next)
    {
      unsigned int bl = rtx_to_bits (w->orig_x);
      if (size_word == bl)
        return w;
    }
  return NULL;
}

/* Returns the superweb for SUBWEB.  */

struct web *
find_web_for_subweb_1 (subweb)
     struct web *subweb;
{
  while (subweb->parent_web)
    subweb = subweb->parent_web;
  return subweb;
}

/* Determine if two hard register sets intersect.
   Return 1 if they do.  */

int
hard_regs_intersect_p (a, b)
     HARD_REG_SET *a, *b;
{
  HARD_REG_SET c;
  COPY_HARD_REG_SET (c, *a);
  AND_HARD_REG_SET (c, *b);
  GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
  return 1;
lose:
  return 0;
}

/* Allocate and initialize the memory necessary for one pass of the
   register allocator.  */

static void
alloc_mem (df)
     struct df *df;
{
  int i;
  ra_build_realloc (df);
  if (!live_at_end)
    {
      live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
					* sizeof (bitmap));
      for (i = 0; i < last_basic_block + 2; i++)
	live_at_end[i] = BITMAP_XMALLOC ();
      live_at_end += 2;
    }
  create_insn_info (df);
}

/* Free the memory which isn't necessary for the next pass.  */

static void
free_mem (df)
     struct df *df ATTRIBUTE_UNUSED;
{
  free_insn_info ();
  ra_build_free ();
}

/* Free all memory allocated for the register allocator.  Used, when
   it's done.  */

static void
free_all_mem (df)
     struct df *df;
{
  unsigned int i;
  live_at_end -= 2;
  for (i = 0; i < (unsigned)last_basic_block + 2; i++)
    BITMAP_XFREE (live_at_end[i]);
  free (live_at_end);

  ra_colorize_free_all ();
  ra_build_free_all (df);
  obstack_free (&ra_obstack, NULL);
}

static long ticks_build;
static long ticks_rebuild;

/* Perform one pass of allocation.  Returns nonzero, if some spill code
   was added, i.e. if the allocator needs to rerun.  */

static int
one_pass (df, rebuild)
     struct df *df;
     int rebuild;
{
  long ticks = clock ();
  int something_spilled;
  remember_conflicts = 0;

  /* Build the complete interference graph, or if this is not the first
     pass, rebuild it incrementally.  */
  build_i_graph (df);

  /* From now on, if we create new conflicts, we need to remember the
     initial list of conflicts per web.  */
  remember_conflicts = 1;
  if (!rebuild)
    dump_igraph_machine ();

  /* Colorize the I-graph.  This results in either a list of
     spilled_webs, in which case we need to run the spill phase, and
     rerun the allocator, or that list is empty, meaning we are done.  */
  ra_colorize_graph (df);

  last_max_uid = get_max_uid ();
  /* actual_spill() might change WEBS(SPILLED) and even empty it,
     so we need to remember it's state.  */
  something_spilled = !!WEBS(SPILLED);

  /* Add spill code if necessary.  */
  if (something_spilled)
    actual_spill ();

  ticks = clock () - ticks;
  if (rebuild)
    ticks_rebuild += ticks;
  else
    ticks_build += ticks;
  return something_spilled;
}

/* Initialize various arrays for the register allocator.  */

static void
init_ra ()
{
  int i;
  HARD_REG_SET rs;
#ifdef ELIMINABLE_REGS
  static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
  unsigned int j;
#endif
  int need_fp
    = (! flag_omit_frame_pointer
#ifdef EXIT_IGNORE_STACK
       || (current_function_calls_alloca && EXIT_IGNORE_STACK)
#endif
       || FRAME_POINTER_REQUIRED);

  ra_colorize_init ();

  /* We can't ever use any of the fixed regs.  */
  COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);

  /* Additionally don't even try to use hardregs, which we already
     know are not eliminable.  This includes also either the
     hard framepointer or all regs which are eliminable into the
     stack pointer, if need_fp is set.  */
#ifdef ELIMINABLE_REGS
  for (j = 0; j < ARRAY_SIZE (eliminables); j++)
    {
      if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
	  || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
	for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
	  SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
    }
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
  if (need_fp)
    for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
      SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
#endif

#else
  if (need_fp)
    for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
      SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
#endif

  /* Stack and argument pointer are also rather useless to us.  */
  for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
    SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);

  for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
    SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);

  for (i = 0; i < 256; i++)
    {
      unsigned char byte = ((unsigned) i) & 0xFF;
      unsigned char count = 0;
      while (byte)
	{
	  if (byte & 1)
	    count++;
	  byte >>= 1;
	}
      byte2bitcount[i] = count;
    }

  for (i = 0; i < N_REG_CLASSES; i++)
    {
      int size;
      COPY_HARD_REG_SET (rs, reg_class_contents[i]);
      AND_COMPL_HARD_REG_SET (rs, never_use_colors);
      size = hard_regs_count (rs);
      num_free_regs[i] = size;
      COPY_HARD_REG_SET (usable_regs[i], rs);
    }

  /* Setup hardregs_for_mode[].
     We are not interested only in the beginning of a multi-reg, but in
     all the hardregs involved.  Maybe HARD_REGNO_MODE_OK() only ok's
     for beginnings.  */
  for (i = 0; i < NUM_MACHINE_MODES; i++)
    {
      int reg, size;
      CLEAR_HARD_REG_SET (rs);
      for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
	if (HARD_REGNO_MODE_OK (reg, i)
	    /* Ignore VOIDmode and similar things.  */
	    && (size = HARD_REGNO_NREGS (reg, i)) != 0
	    && (reg + size) <= FIRST_PSEUDO_REGISTER)
	  {
	    while (size--)
	      SET_HARD_REG_BIT (rs, reg + size);
	  }
      COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
    }

  for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
       an_unusable_color++)
    if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
      break;
  if (an_unusable_color == FIRST_PSEUDO_REGISTER)
    abort ();

  orig_max_uid = get_max_uid ();
  compute_bb_for_insn ();
  ra_reg_renumber = NULL;
  insns_with_deaths = sbitmap_alloc (orig_max_uid);
  death_insns_max_uid = orig_max_uid;
  sbitmap_ones (insns_with_deaths);
  gcc_obstack_init (&ra_obstack);
}

/* Check the consistency of DF.  This aborts if it violates some
   invariances we expect.  */

static void
check_df (df)
     struct df *df;
{
  struct df_link *link;
  rtx insn;
  int regno;
  unsigned int ui;
  bitmap b = BITMAP_XMALLOC ();
  bitmap empty_defs = BITMAP_XMALLOC ();
  bitmap empty_uses = BITMAP_XMALLOC ();

  /* Collect all the IDs of NULL references in the ID->REF arrays,
     as df.c leaves them when updating the df structure.  */
  for (ui = 0; ui < df->def_id; ui++)
    if (!df->defs[ui])
      bitmap_set_bit (empty_defs, ui);
  for (ui = 0; ui < df->use_id; ui++)
    if (!df->uses[ui])
      bitmap_set_bit (empty_uses, ui);

  /* For each insn we check if the chain of references contain each
     ref only once, doesn't contain NULL refs, or refs whose ID is invalid
     (it df->refs[id] element is NULL).  */
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    if (INSN_P (insn))
      {
	bitmap_clear (b);
	for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
	  if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
	      || bitmap_bit_p (b, DF_REF_ID (link->ref)))
	    abort ();
	  else
	    bitmap_set_bit (b, DF_REF_ID (link->ref));

	bitmap_clear (b);
	for (link = DF_INSN_USES (df, insn); link; link = link->next)
	  if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
	      || bitmap_bit_p (b, DF_REF_ID (link->ref)))
	    abort ();
	  else
	    bitmap_set_bit (b, DF_REF_ID (link->ref));
      }

  /* Now the same for the chains per register number.  */
  for (regno = 0; regno < max_reg_num (); regno++)
    {
      bitmap_clear (b);
      for (link = df->regs[regno].defs; link; link = link->next)
	if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
	    || bitmap_bit_p (b, DF_REF_ID (link->ref)))
	  abort ();
	else
	  bitmap_set_bit (b, DF_REF_ID (link->ref));

      bitmap_clear (b);
      for (link = df->regs[regno].uses; link; link = link->next)
	if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
	    || bitmap_bit_p (b, DF_REF_ID (link->ref)))
	  abort ();
	else
	  bitmap_set_bit (b, DF_REF_ID (link->ref));
    }

  BITMAP_XFREE (empty_uses);
  BITMAP_XFREE (empty_defs);
  BITMAP_XFREE (b);
}

/* Main register allocator entry point.  */

void
reg_alloc ()
{
  int changed;
  FILE *ra_dump_file = rtl_dump_file;
  rtx last = get_last_insn ();

  if (! INSN_P (last))
    last = prev_real_insn (last);
  /* If this is an empty function we shouldn't do all the following,
     but instead just setup what's necessary, and return.  */

  /* We currently rely on the existance of the return value USE as
     one of the last insns.  Add it if it's not there anymore.  */
  if (last)
    {
      edge e;
      for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
	{
	  basic_block bb = e->src;
	  last = bb->end;
	  if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
	    {
	      rtx insns;
	      start_sequence ();
	      use_return_register ();
	      insns = get_insns ();
	      end_sequence ();
	      emit_insn_after (insns, last);
	    }
	}
    }

  /* Setup debugging levels.  */
  switch (0)
    {
      /* Some usefull presets of the debug level, I often use.  */
      case 0: debug_new_regalloc = DUMP_EVER; break;
      case 1: debug_new_regalloc = DUMP_COSTS; break;
      case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
      case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
      case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
	      break;
      case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
	      DUMP_CONSTRAINTS;
	      break;
      case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
    }
  if (!rtl_dump_file)
    debug_new_regalloc = 0;

  /* Run regclass first, so we know the preferred and alternate classes
     for each pseudo.  Deactivate emitting of debug info, if it's not
     explicitely requested.  */
  if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
    rtl_dump_file = NULL;
  regclass (get_insns (), max_reg_num (), rtl_dump_file);
  rtl_dump_file = ra_dump_file;

  /* We don't use those NOTEs, and as we anyway change all registers,
     they only make problems later.  */
  count_or_remove_death_notes (NULL, 1);

  /* Initialize the different global arrays and regsets.  */
  init_ra ();

  /* And some global variables.  */
  ra_pass = 0;
  no_new_pseudos = 0;
  max_normal_pseudo = (unsigned) max_reg_num ();
  ra_rewrite_init ();
  last_def_id = 0;
  last_use_id = 0;
  last_num_webs = 0;
  last_max_uid = 0;
  last_check_uses = NULL;
  live_at_end = NULL;
  WEBS(INITIAL) = NULL;
  WEBS(FREE) = NULL;
  memset (hardreg2web, 0, sizeof (hardreg2web));
  ticks_build = ticks_rebuild = 0;

  /* The default is to use optimistic coalescing with interference
     region spilling, without biased coloring.  */
  flag_ra_biased = 0;
  flag_ra_spill_every_use = 0;
  flag_ra_improved_spilling = 1;
  flag_ra_ir_spilling = 1;
  flag_ra_break_aliases = 0;
  flag_ra_optimistic_coalescing = 1;
  flag_ra_merge_spill_costs = 1;
  if (flag_ra_optimistic_coalescing)
    flag_ra_break_aliases = 1;
  flag_ra_dump_notes = 0;

  /* Allocate the global df structure.  */
  df = df_init ();

  /* This is the main loop, calling one_pass as long as there are still
     some spilled webs.  */
  do
    {
      ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
      if (ra_pass++ > 40)
	internal_error ("Didn't find a coloring.\n");

      /* First collect all the register refs and put them into
	 chains per insn, and per regno.  In later passes only update
         that info from the new and modified insns.  */
      df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
		  DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN);

      if ((debug_new_regalloc & DUMP_DF) != 0)
	{
	  rtx insn;
	  df_dump (df, DF_HARD_REGS, rtl_dump_file);
	  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
            if (INSN_P (insn))
	      df_insn_debug_regno (df, insn, rtl_dump_file);
	}
      check_df (df);

      /* Now allocate the memory needed for this pass, or (if it's not the
	 first pass), reallocate only additional memory.  */
      alloc_mem (df);

      /* Build and colorize the interference graph, and possibly emit
	 spill insns.  This also might delete certain move insns.  */
      changed = one_pass (df, ra_pass > 1);

      /* If that produced no changes, the graph was colorizable.  */
      if (!changed)
	{
	  /* Change the insns to refer to the new pseudos (one per web).  */
          emit_colors (df);
	  /* Already setup a preliminary reg_renumber[] array, but don't
	     free our own version.  reg_renumber[] will again be destroyed
	     later.  We right now need it in dump_constraints() for
	     constrain_operands(1) whose subproc sometimes reference
	     it (because we are checking strictly, i.e. as if
	     after reload).  */
	  setup_renumber (0);
	  /* Delete some more of the coalesced moves.  */
	  delete_moves ();
	  dump_constraints ();
	}
      else
	{
	  /* If there were changes, this means spill code was added,
	     therefore repeat some things, including some initialization
	     of global data structures.  */
	  if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
	    rtl_dump_file = NULL;
	  /* We have new pseudos (the stackwebs).  */
	  allocate_reg_info (max_reg_num (), FALSE, FALSE);
	  /* And new insns.  */
	  compute_bb_for_insn ();
	  /* Some of them might be dead.  */
	  delete_trivially_dead_insns (get_insns (), max_reg_num ());
	  /* Those new pseudos need to have their REFS count set.  */
	  reg_scan_update (get_insns (), NULL, max_regno);
	  max_regno = max_reg_num ();
	  /* And they need usefull classes too.  */
	  regclass (get_insns (), max_reg_num (), rtl_dump_file);
	  rtl_dump_file = ra_dump_file;

	  /* Remember the number of defs and uses, so we can distinguish
	     new from old refs in the next pass.  */
	  last_def_id = df->def_id;
	  last_use_id = df->use_id;
	}

      /* Output the graph, and possibly the current insn sequence.  */
      dump_ra (df);
      if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
	{
	  ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
	  fflush (rtl_dump_file);
	}

      /* Reset the web lists.  */
      reset_lists ();
      free_mem (df);
    }
  while (changed);

  /* We are done with allocation, free all memory and output some
     debug info.  */
  free_all_mem (df);
  df_finish (df);
  if ((debug_new_regalloc & DUMP_RESULTS) == 0)
    dump_cost (DUMP_COSTS);
  ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
  ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
  if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
    ra_print_rtl_with_bb (rtl_dump_file, get_insns ());

  /* We might have new pseudos, so allocate the info arrays for them.  */
  if ((debug_new_regalloc & DUMP_SM) == 0)
    rtl_dump_file = NULL;
  no_new_pseudos = 0;
  allocate_reg_info (max_reg_num (), FALSE, FALSE);
  no_new_pseudos = 1;
  rtl_dump_file = ra_dump_file;

  /* Some spill insns could've been inserted after trapping calls, i.e.
     at the end of a basic block, which really ends at that call.
     Fixup that breakages by adjusting basic block boundaries.  */
  fixup_abnormal_edges ();

  /* Cleanup the flow graph.  */
  if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
    rtl_dump_file = NULL;
  life_analysis (get_insns (), rtl_dump_file,
		 PROP_DEATH_NOTES | PROP_LOG_LINKS  | PROP_REG_INFO);
  cleanup_cfg (CLEANUP_EXPENSIVE);
  recompute_reg_usage (get_insns (), TRUE);
  if (rtl_dump_file)
    dump_flow_info (rtl_dump_file);
  rtl_dump_file = ra_dump_file;

  /* update_equiv_regs() can't be called after register allocation.
     It might delete some pseudos, and insert other insns setting
     up those pseudos in different places.  This of course screws up
     the allocation because that may destroy a hardreg for another
     pseudo.
     XXX we probably should do something like that on our own.  I.e.
     creating REG_EQUIV notes.  */
  /*update_equiv_regs ();*/

  /* Setup the reg_renumber[] array for reload.  */
  setup_renumber (1);
  sbitmap_free (insns_with_deaths);

  /* Remove REG_DEAD notes which are incorrectly set.  See the docu
     of that function.  */
  remove_suspicious_death_notes ();

  if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
    ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
  dump_static_insn_cost (rtl_dump_file,
			 "after allocation/spilling, before reload", NULL);

  /* Allocate the reg_equiv_memory_loc array for reload.  */
  reg_equiv_memory_loc = (rtx *) xcalloc (max_regno, sizeof (rtx));
  /* And possibly initialize it.  */
  allocate_initial_values (reg_equiv_memory_loc);
  /* And one last regclass pass just before reload.  */
  regclass (get_insns (), max_reg_num (), rtl_dump_file);
}

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