gcc/ra.c

   1 /* Graph coloring register allocator
   2    Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   3    Contributed by Michael Matz <matz@suse.de>
   4    and Daniel Berlin <dan@cgsoftware.com>.
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify it under the
   9    terms of the GNU General Public License as published by the Free Software
  10    Foundation; either version 2, or (at your option) any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  15    details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with GCC; see the file COPYING.  If not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tm_p.h"
  27 #include "insn-config.h"
  28 #include "recog.h"
  29 #include "reload.h"
  30 #include "integrate.h"
  31 #include "function.h"
  32 #include "regs.h"
  33 #include "obstack.h"
  34 #include "hard-reg-set.h"
  35 #include "basic-block.h"
  36 #include "df.h"
  37 #include "expr.h"
  38 #include "output.h"
  39 #include "toplev.h"
  40 #include "flags.h"
  41 #include "ra.h"
  42
  43 /* This is the toplevel file of a graph coloring register allocator.
  44    It is able to act like a George & Appel allocator, i.e. with iterative
  45    coalescing plus spill coalescing/propagation.
  46    And it can act as a traditional Briggs allocator, although with
  47    optimistic coalescing.  Additionally it has a custom pass, which
  48    tries to reduce the overall cost of the colored graph.
  49
  50    We support two modes of spilling: spill-everywhere, which is extremely
  51    fast, and interference region spilling, which reduces spill code to a
  52    large extent, but is slower.
  53
  54    Helpful documents:
  55
  56    Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
  57    coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
  58    428-455.
  59
  60    Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
  61    minimization via interference region spilling. In Proc. ACM SIGPLAN '97
  62    Conf. on Prog. Language Design and Implementation. ACM, 287-295.
  63
  64    George, L., Appel, A.W. 1996.  Iterated register coalescing.
  65    ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
  66
  67 */
  68
  69 /* This file contains the main entry point (reg_alloc), some helper routines
  70    used by more than one file of the register allocator, and the toplevel
  71    driver procedure (one_pass).  */
  72
  73 /* Things, one might do somewhen:
  74
  75    * Lattice based rematerialization
  76    * create definitions of ever-life regs at the beginning of
  77      the insn chain
  78    * insert loads as soon, stores as late as possible
  79    * insert spill insns as outward as possible (either looptree, or LCM)
  80    * reuse stack-slots
  81    * delete coalesced insns.  Partly done.  The rest can only go, when we get
  82      rid of reload.
  83    * don't destroy coalescing information completely when spilling
  84    * use the constraints from asms
  85   */
  86
  87 static struct obstack ra_obstack;
  88 static void create_insn_info PARAMS ((struct df *));
  89 static void free_insn_info PARAMS ((void));
  90 static void alloc_mem PARAMS ((struct df *));
  91 static void free_mem PARAMS ((struct df *));
  92 static void free_all_mem PARAMS ((struct df *df));
  93 static int one_pass PARAMS ((struct df *, int));
  94 static void check_df PARAMS ((struct df *));
  95 static void init_ra PARAMS ((void));
  96
  97 void reg_alloc PARAMS ((void));
  98
  99 /* These global variables are "internal" to the register allocator.
 100    They are all documented at their declarations in ra.h.  */
 101
 102 /* Somewhen we want to get rid of one of those sbitmaps.
 103    (for now I need the sup_igraph to note if there is any conflict between
 104    parts of webs at all.  I can't use igraph for this, as there only the real
 105    conflicts are noted.)  This is only used to prevent coalescing two
 106    conflicting webs, were only parts of them are in conflict.  */
 107 sbitmap igraph;
 108 sbitmap sup_igraph;
 109
 110 /* Note the insns not inserted by the allocator, where we detected any
 111    deaths of pseudos.  It is used to detect closeness of defs and uses.
 112    In the first pass this is empty (we could initialize it from REG_DEAD
 113    notes), in the other passes it is left from the pass before.  */
 114 sbitmap insns_with_deaths;
 115 int death_insns_max_uid;
 116
 117 struct web_part *web_parts;
 118
 119 unsigned int num_webs;
 120 unsigned int num_subwebs;
 121 unsigned int num_allwebs;
 122 struct web **id2web;
 123 struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
 124 struct web **def2web;
 125 struct web **use2web;
 126 struct move_list *wl_moves;
 127 int ra_max_regno;
 128 short *ra_reg_renumber;
 129 struct df *df;
 130 bitmap *live_at_end;
 131 int ra_pass;
 132 unsigned int max_normal_pseudo;
 133 int an_unusable_color;
 134
 135 /* The different lists on which a web can be (based on the type).  */
 136 struct dlist *web_lists[(int) LAST_NODE_TYPE];
 137
 138 unsigned int last_def_id;
 139 unsigned int last_use_id;
 140 unsigned int last_num_webs;
 141 int last_max_uid;
 142 sbitmap last_check_uses;
 143 unsigned int remember_conflicts;
 144
 145 int orig_max_uid;
 146
 147 HARD_REG_SET never_use_colors;
 148 HARD_REG_SET usable_regs[N_REG_CLASSES];
 149 unsigned int num_free_regs[N_REG_CLASSES];
 150 HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
 151 HARD_REG_SET invalid_mode_change_regs;
 152 unsigned char byte2bitcount[256];
 153
 154 unsigned int debug_new_regalloc = -1;
 155 int flag_ra_biased = 0;
 156 int flag_ra_improved_spilling = 0;
 157 int flag_ra_ir_spilling = 0;
 158 int flag_ra_optimistic_coalescing = 0;
 159 int flag_ra_break_aliases = 0;
 160 int flag_ra_merge_spill_costs = 0;
 161 int flag_ra_spill_every_use = 0;
 162 int flag_ra_dump_notes = 0;
 163
 164 /* Fast allocation of small objects, which live until the allocator
 165    is done.  Allocate an object of SIZE bytes.  */
 166
 167 void *
 168 ra_alloc (size)
 169      size_t size;
 170 {
 171   return obstack_alloc (&ra_obstack, size);
 172 }
 173
 174 /* Like ra_alloc(), but clear the returned memory.  */
 175
 176 void *
 177 ra_calloc (size)
 178      size_t size;
 179 {
 180   void *p = obstack_alloc (&ra_obstack, size);
 181   memset (p, 0, size);
 182   return p;
 183 }
 184
 185 /* Returns the number of hardregs in HARD_REG_SET RS.  */
 186
 187 int
 188 hard_regs_count (rs)
 189      HARD_REG_SET rs;
 190 {
 191   int count = 0;
 192 #ifdef HARD_REG_SET
 193   while (rs)
 194     {
 195       unsigned char byte = rs & 0xFF;
 196       rs >>= 8;
 197       /* Avoid memory access, if nothing is set.  */
 198       if (byte)
 199         count += byte2bitcount[byte];
 200     }
 201 #else
 202   unsigned int ofs;
 203   for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
 204     {
 205       HARD_REG_ELT_TYPE elt = rs[ofs];
 206       while (elt)
 207         {
 208           unsigned char byte = elt & 0xFF;
 209           elt >>= 8;
 210           if (byte)
 211             count += byte2bitcount[byte];
 212         }
 213     }
 214 #endif
 215   return count;
 216 }
 217
 218 /* Basically like emit_move_insn (i.e. validifies constants and such),
 219    but also handle MODE_CC moves (but then the operands must already
 220    be basically valid.  */
 221
 222 rtx
 223 ra_emit_move_insn (x, y)
 224      rtx x, y;
 225 {
 226   enum machine_mode mode = GET_MODE (x);
 227   if (GET_MODE_CLASS (mode) == MODE_CC)
 228     return emit_insn (gen_move_insn (x, y));
 229   else
 230     return emit_move_insn (x, y);
 231 }
 232
 233 int insn_df_max_uid;
 234 struct ra_insn_info *insn_df;
 235 static struct ref **refs_for_insn_df;
 236
 237 /* Create the insn_df structure for each insn to have fast access to
 238    all valid defs and uses in an insn.  */
 239
 240 static void
 241 create_insn_info (df)
 242      struct df *df;
 243 {
 244   rtx insn;
 245   struct ref **act_refs;
 246   insn_df_max_uid = get_max_uid ();
 247   insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
 248   refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
 249   act_refs = refs_for_insn_df;
 250   /* We create those things backwards to mimic the order in which
 251      the insns are visited in rewrite_program2() and live_in().  */
 252   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 253     {
 254       int uid = INSN_UID (insn);
 255       unsigned int n;
 256       struct df_link *link;
 257       if (!INSN_P (insn))
 258         continue;
 259       for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
 260         if (link->ref
 261             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 262                 || !TEST_HARD_REG_BIT (never_use_colors,
 263                                        DF_REF_REGNO (link->ref))))
 264           {
 265             if (n == 0)
 266               insn_df[uid].defs = act_refs;
 267             insn_df[uid].defs[n++] = link->ref;
 268           }
 269       act_refs += n;
 270       insn_df[uid].num_defs = n;
 271       for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
 272         if (link->ref
 273             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 274                 || !TEST_HARD_REG_BIT (never_use_colors,
 275                                        DF_REF_REGNO (link->ref))))
 276           {
 277             if (n == 0)
 278               insn_df[uid].uses = act_refs;
 279             insn_df[uid].uses[n++] = link->ref;
 280           }
 281       act_refs += n;
 282       insn_df[uid].num_uses = n;
 283     }
 284   if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
 285     abort ();
 286 }
 287
 288 /* Free the insn_df structures.  */
 289
 290 static void
 291 free_insn_info ()
 292 {
 293   free (refs_for_insn_df);
 294   refs_for_insn_df = NULL;
 295   free (insn_df);
 296   insn_df = NULL;
 297   insn_df_max_uid = 0;
 298 }
 299
 300 /* Search WEB for a subweb, which represents REG.  REG needs to
 301    be a SUBREG, and the inner reg of it needs to be the one which is
 302    represented by WEB.  Returns the matching subweb or NULL.  */
 303
 304 struct web *
 305 find_subweb (web, reg)
 306      struct web *web;
 307      rtx reg;
 308 {
 309   struct web *w;
 310   if (GET_CODE (reg) != SUBREG)
 311     abort ();
 312   for (w = web->subreg_next; w; w = w->subreg_next)
 313     if (GET_MODE (w->orig_x) == GET_MODE (reg)
 314         && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
 315       return w;
 316   return NULL;
 317 }
 318
 319 /* Similar to find_subweb(), but matches according to SIZE_WORD,
 320    a collection of the needed size and offset (in bytes).  */
 321
 322 struct web *
 323 find_subweb_2 (web, size_word)
 324      struct web *web;
 325      unsigned int size_word;
 326 {
 327   struct web *w = web;
 328   if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
 329     /* size_word == size means BYTE_BEGIN(size_word) == 0.  */
 330     return web;
 331   for (w = web->subreg_next; w; w = w->subreg_next)
 332     {
 333       unsigned int bl = rtx_to_bits (w->orig_x);
 334       if (size_word == bl)
 335         return w;
 336     }
 337   return NULL;
 338 }
 339
 340 /* Returns the superweb for SUBWEB.  */
 341
 342 struct web *
 343 find_web_for_subweb_1 (subweb)
 344      struct web *subweb;
 345 {
 346   while (subweb->parent_web)
 347     subweb = subweb->parent_web;
 348   return subweb;
 349 }
 350
 351 /* Determine if two hard register sets intersect.
 352    Return 1 if they do.  */
 353
 354 int
 355 hard_regs_intersect_p (a, b)
 356      HARD_REG_SET *a, *b;
 357 {
 358   HARD_REG_SET c;
 359   COPY_HARD_REG_SET (c, *a);
 360   AND_HARD_REG_SET (c, *b);
 361   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
 362   return 1;
 363 lose:
 364   return 0;
 365 }
 366
 367 /* Allocate and initialize the memory necessary for one pass of the
 368    register allocator.  */
 369
 370 static void
 371 alloc_mem (df)
 372      struct df *df;
 373 {
 374   int i;
 375   ra_build_realloc (df);
 376   if (!live_at_end)
 377     {
 378       live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
 379                                         * sizeof (bitmap));
 380       for (i = 0; i < last_basic_block + 2; i++)
 381         live_at_end[i] = BITMAP_XMALLOC ();
 382       live_at_end += 2;
 383     }
 384   create_insn_info (df);
 385 }
 386
 387 /* Free the memory which isn't necessary for the next pass.  */
 388
 389 static void
 390 free_mem (df)
 391      struct df *df ATTRIBUTE_UNUSED;
 392 {
 393   free_insn_info ();
 394   ra_build_free ();
 395 }
 396
 397 /* Free all memory allocated for the register allocator.  Used, when
 398    it's done.  */
 399
 400 static void
 401 free_all_mem (df)
 402      struct df *df;
 403 {
 404   unsigned int i;
 405   live_at_end -= 2;
 406   for (i = 0; i < (unsigned)last_basic_block + 2; i++)
 407     BITMAP_XFREE (live_at_end[i]);
 408   free (live_at_end);
 409
 410   ra_colorize_free_all ();
 411   ra_build_free_all (df);
 412   obstack_free (&ra_obstack, NULL);
 413 }
 414
 415 static long ticks_build;
 416 static long ticks_rebuild;
 417
 418 /* Perform one pass of allocation.  Returns nonzero, if some spill code
 419    was added, i.e. if the allocator needs to rerun.  */
 420
 421 static int
 422 one_pass (df, rebuild)
 423      struct df *df;
 424      int rebuild;
 425 {
 426   long ticks = clock ();
 427   int something_spilled;
 428   remember_conflicts = 0;
 429
 430   /* Build the complete interference graph, or if this is not the first
 431      pass, rebuild it incrementally.  */
 432   build_i_graph (df);
 433
 434   /* From now on, if we create new conflicts, we need to remember the
 435      initial list of conflicts per web.  */
 436   remember_conflicts = 1;
 437   if (!rebuild)
 438     dump_igraph_machine ();
 439
 440   /* Colorize the I-graph.  This results in either a list of
 441      spilled_webs, in which case we need to run the spill phase, and
 442      rerun the allocator, or that list is empty, meaning we are done.  */
 443   ra_colorize_graph (df);
 444
 445   last_max_uid = get_max_uid ();
 446   /* actual_spill() might change WEBS(SPILLED) and even empty it,
 447      so we need to remember it's state.  */
 448   something_spilled = !!WEBS(SPILLED);
 449
 450   /* Add spill code if necessary.  */
 451   if (something_spilled)
 452     actual_spill ();
 453
 454   ticks = clock () - ticks;
 455   if (rebuild)
 456     ticks_rebuild += ticks;
 457   else
 458     ticks_build += ticks;
 459   return something_spilled;
 460 }
 461
 462 /* Initialize various arrays for the register allocator.  */
 463
 464 static void
 465 init_ra ()
 466 {
 467   int i;
 468   HARD_REG_SET rs;
 469 #ifdef ELIMINABLE_REGS
 470   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
 471   unsigned int j;
 472 #endif
 473   int need_fp
 474     = (! flag_omit_frame_pointer
 475 #ifdef EXIT_IGNORE_STACK
 476        || (current_function_calls_alloca && EXIT_IGNORE_STACK)
 477 #endif
 478        || FRAME_POINTER_REQUIRED);
 479
 480   ra_colorize_init ();
 481
 482   /* We can't ever use any of the fixed regs.  */
 483   COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
 484
 485   /* Additionally don't even try to use hardregs, which we already
 486      know are not eliminable.  This includes also either the
 487      hard framepointer or all regs which are eliminable into the
 488      stack pointer, if need_fp is set.  */
 489 #ifdef ELIMINABLE_REGS
 490   for (j = 0; j < ARRAY_SIZE (eliminables); j++)
 491     {
 492       if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
 493           || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
 494         for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
 495           SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
 496     }
 497 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 498   if (need_fp)
 499     for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
 500       SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
 501 #endif
 502
 503 #else
 504   if (need_fp)
 505     for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
 506       SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
 507 #endif
 508
 509   /* Stack and argument pointer are also rather useless to us.  */
 510   for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
 511     SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
 512
 513   for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
 514     SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
 515
 516   for (i = 0; i < 256; i++)
 517     {
 518       unsigned char byte = ((unsigned) i) & 0xFF;
 519       unsigned char count = 0;
 520       while (byte)
 521         {
 522           if (byte & 1)
 523             count++;
 524           byte >>= 1;
 525         }
 526       byte2bitcount[i] = count;
 527     }
 528
 529   for (i = 0; i < N_REG_CLASSES; i++)
 530     {
 531       int size;
 532       COPY_HARD_REG_SET (rs, reg_class_contents[i]);
 533       AND_COMPL_HARD_REG_SET (rs, never_use_colors);
 534       size = hard_regs_count (rs);
 535       num_free_regs[i] = size;
 536       COPY_HARD_REG_SET (usable_regs[i], rs);
 537     }
 538
 539   /* Setup hardregs_for_mode[].
 540      We are not interested only in the beginning of a multi-reg, but in
 541      all the hardregs involved.  Maybe HARD_REGNO_MODE_OK() only ok's
 542      for beginnings.  */
 543   for (i = 0; i < NUM_MACHINE_MODES; i++)
 544     {
 545       int reg, size;
 546       CLEAR_HARD_REG_SET (rs);
 547       for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
 548         if (HARD_REGNO_MODE_OK (reg, i)
 549             /* Ignore VOIDmode and similar things.  */
 550             && (size = HARD_REGNO_NREGS (reg, i)) != 0
 551             && (reg + size) <= FIRST_PSEUDO_REGISTER)
 552           {
 553             while (size--)
 554               SET_HARD_REG_BIT (rs, reg + size);
 555           }
 556       COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
 557     }
 558
 559   CLEAR_HARD_REG_SET (invalid_mode_change_regs);
 560 #ifdef CANNOT_CHANGE_MODE_CLASS
 561   if (0)
 562   for (i = 0; i < NUM_MACHINE_MODES; i++)
 563     {
 564       enum machine_mode from = (enum machine_mode) i;
 565       enum machine_mode to;
 566       for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
 567         {
 568           int r;
 569           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 570             if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
 571               SET_HARD_REG_BIT (invalid_mode_change_regs, r);
 572         }
 573     }
 574 #endif
 575
 576   for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
 577        an_unusable_color++)
 578     if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
 579       break;
 580   if (an_unusable_color == FIRST_PSEUDO_REGISTER)
 581     abort ();
 582
 583   orig_max_uid = get_max_uid ();
 584   compute_bb_for_insn ();
 585   ra_reg_renumber = NULL;
 586   insns_with_deaths = sbitmap_alloc (orig_max_uid);
 587   death_insns_max_uid = orig_max_uid;
 588   sbitmap_ones (insns_with_deaths);
 589   gcc_obstack_init (&ra_obstack);
 590 }
 591
 592 /* Check the consistency of DF.  This aborts if it violates some
 593    invariances we expect.  */
 594
 595 static void
 596 check_df (df)
 597      struct df *df;
 598 {
 599   struct df_link *link;
 600   rtx insn;
 601   int regno;
 602   unsigned int ui;
 603   bitmap b = BITMAP_XMALLOC ();
 604   bitmap empty_defs = BITMAP_XMALLOC ();
 605   bitmap empty_uses = BITMAP_XMALLOC ();
 606
 607   /* Collect all the IDs of NULL references in the ID->REF arrays,
 608      as df.c leaves them when updating the df structure.  */
 609   for (ui = 0; ui < df->def_id; ui++)
 610     if (!df->defs[ui])
 611       bitmap_set_bit (empty_defs, ui);
 612   for (ui = 0; ui < df->use_id; ui++)
 613     if (!df->uses[ui])
 614       bitmap_set_bit (empty_uses, ui);
 615
 616   /* For each insn we check if the chain of references contain each
 617      ref only once, doesn't contain NULL refs, or refs whose ID is invalid
 618      (it df->refs[id] element is NULL).  */
 619   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 620     if (INSN_P (insn))
 621       {
 622         bitmap_clear (b);
 623         for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
 624           if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 625               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 626             abort ();
 627           else
 628             bitmap_set_bit (b, DF_REF_ID (link->ref));
 629
 630         bitmap_clear (b);
 631         for (link = DF_INSN_USES (df, insn); link; link = link->next)
 632           if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 633               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 634             abort ();
 635           else
 636             bitmap_set_bit (b, DF_REF_ID (link->ref));
 637       }
 638
 639   /* Now the same for the chains per register number.  */
 640   for (regno = 0; regno < max_reg_num (); regno++)
 641     {
 642       bitmap_clear (b);
 643       for (link = df->regs[regno].defs; link; link = link->next)
 644         if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 645             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 646           abort ();
 647         else
 648           bitmap_set_bit (b, DF_REF_ID (link->ref));
 649
 650       bitmap_clear (b);
 651       for (link = df->regs[regno].uses; link; link = link->next)
 652         if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 653             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 654           abort ();
 655         else
 656           bitmap_set_bit (b, DF_REF_ID (link->ref));
 657     }
 658
 659   BITMAP_XFREE (empty_uses);
 660   BITMAP_XFREE (empty_defs);
 661   BITMAP_XFREE (b);
 662 }
 663
 664 /* Main register allocator entry point.  */
 665
 666 void
 667 reg_alloc ()
 668 {
 669   int changed;
 670   FILE *ra_dump_file = rtl_dump_file;
 671   rtx last = get_last_insn ();
 672
 673   if (! INSN_P (last))
 674     last = prev_real_insn (last);
 675   /* If this is an empty function we shouldn't do all the following,
 676      but instead just setup what's necessary, and return.  */
 677
 678   /* We currently rely on the existence of the return value USE as
 679      one of the last insns.  Add it if it's not there anymore.  */
 680   if (last)
 681     {
 682       edge e;
 683       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 684         {
 685           basic_block bb = e->src;
 686           last = bb->end;
 687           if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
 688             {
 689               rtx insns;
 690               start_sequence ();
 691               use_return_register ();
 692               insns = get_insns ();
 693               end_sequence ();
 694               emit_insn_after (insns, last);
 695             }
 696         }
 697     }
 698
 699   /* Setup debugging levels.  */
 700   switch (0)
 701     {
 702       /* Some useful presets of the debug level, I often use.  */
 703       case 0: debug_new_regalloc = DUMP_EVER; break;
 704       case 1: debug_new_regalloc = DUMP_COSTS; break;
 705       case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
 706       case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
 707       case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
 708               break;
 709       case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
 710               DUMP_CONSTRAINTS;
 711               break;
 712       case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
 713     }
 714   if (!rtl_dump_file)
 715     debug_new_regalloc = 0;
 716
 717   /* Run regclass first, so we know the preferred and alternate classes
 718      for each pseudo.  Deactivate emitting of debug info, if it's not
 719      explicitly requested.  */
 720   if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 721     rtl_dump_file = NULL;
 722   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 723   rtl_dump_file = ra_dump_file;
 724
 725   /* We don't use those NOTEs, and as we anyway change all registers,
 726      they only make problems later.  */
 727   count_or_remove_death_notes (NULL, 1);
 728
 729   /* Initialize the different global arrays and regsets.  */
 730   init_ra ();
 731
 732   /* And some global variables.  */
 733   ra_pass = 0;
 734   no_new_pseudos = 0;
 735   max_normal_pseudo = (unsigned) max_reg_num ();
 736   ra_rewrite_init ();
 737   last_def_id = 0;
 738   last_use_id = 0;
 739   last_num_webs = 0;
 740   last_max_uid = 0;
 741   last_check_uses = NULL;
 742   live_at_end = NULL;
 743   WEBS(INITIAL) = NULL;
 744   WEBS(FREE) = NULL;
 745   memset (hardreg2web, 0, sizeof (hardreg2web));
 746   ticks_build = ticks_rebuild = 0;
 747
 748   /* The default is to use optimistic coalescing with interference
 749      region spilling, without biased coloring.  */
 750   flag_ra_biased = 0;
 751   flag_ra_spill_every_use = 0;
 752   flag_ra_improved_spilling = 1;
 753   flag_ra_ir_spilling = 1;
 754   flag_ra_break_aliases = 0;
 755   flag_ra_optimistic_coalescing = 1;
 756   flag_ra_merge_spill_costs = 1;
 757   if (flag_ra_optimistic_coalescing)
 758     flag_ra_break_aliases = 1;
 759   flag_ra_dump_notes = 0;
 760
 761   /* Allocate the global df structure.  */
 762   df = df_init ();
 763
 764   /* This is the main loop, calling one_pass as long as there are still
 765      some spilled webs.  */
 766   do
 767     {
 768       ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
 769       if (ra_pass++ > 40)
 770         internal_error ("Didn't find a coloring.\n");
 771
 772       /* First collect all the register refs and put them into
 773          chains per insn, and per regno.  In later passes only update
 774          that info from the new and modified insns.  */
 775       df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
 776                   DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
 777
 778       if ((debug_new_regalloc & DUMP_DF) != 0)
 779         {
 780           rtx insn;
 781           df_dump (df, DF_HARD_REGS, rtl_dump_file);
 782           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 783             if (INSN_P (insn))
 784               df_insn_debug_regno (df, insn, rtl_dump_file);
 785         }
 786       check_df (df);
 787
 788       /* Now allocate the memory needed for this pass, or (if it's not the
 789          first pass), reallocate only additional memory.  */
 790       alloc_mem (df);
 791
 792       /* Build and colorize the interference graph, and possibly emit
 793          spill insns.  This also might delete certain move insns.  */
 794       changed = one_pass (df, ra_pass > 1);
 795
 796       /* If that produced no changes, the graph was colorizable.  */
 797       if (!changed)
 798         {
 799           /* Change the insns to refer to the new pseudos (one per web).  */
 800           emit_colors (df);
 801           /* Already setup a preliminary reg_renumber[] array, but don't
 802              free our own version.  reg_renumber[] will again be destroyed
 803              later.  We right now need it in dump_constraints() for
 804              constrain_operands(1) whose subproc sometimes reference
 805              it (because we are checking strictly, i.e. as if
 806              after reload).  */
 807           setup_renumber (0);
 808           /* Delete some more of the coalesced moves.  */
 809           delete_moves ();
 810           dump_constraints ();
 811         }
 812       else
 813         {
 814           /* If there were changes, this means spill code was added,
 815              therefore repeat some things, including some initialization
 816              of global data structures.  */
 817           if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 818             rtl_dump_file = NULL;
 819           /* We have new pseudos (the stackwebs).  */
 820           allocate_reg_info (max_reg_num (), FALSE, FALSE);
 821           /* And new insns.  */
 822           compute_bb_for_insn ();
 823           /* Some of them might be dead.  */
 824           delete_trivially_dead_insns (get_insns (), max_reg_num ());
 825           /* Those new pseudos need to have their REFS count set.  */
 826           reg_scan_update (get_insns (), NULL, max_regno);
 827           max_regno = max_reg_num ();
 828           /* And they need useful classes too.  */
 829           regclass (get_insns (), max_reg_num (), rtl_dump_file);
 830           rtl_dump_file = ra_dump_file;
 831
 832           /* Remember the number of defs and uses, so we can distinguish
 833              new from old refs in the next pass.  */
 834           last_def_id = df->def_id;
 835           last_use_id = df->use_id;
 836         }
 837
 838       /* Output the graph, and possibly the current insn sequence.  */
 839       dump_ra (df);
 840       if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
 841         {
 842           ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 843           fflush (rtl_dump_file);
 844         }
 845
 846       /* Reset the web lists.  */
 847       reset_lists ();
 848       free_mem (df);
 849     }
 850   while (changed);
 851
 852   /* We are done with allocation, free all memory and output some
 853      debug info.  */
 854   free_all_mem (df);
 855   df_finish (df);
 856   if ((debug_new_regalloc & DUMP_RESULTS) == 0)
 857     dump_cost (DUMP_COSTS);
 858   ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
 859   ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
 860   if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
 861     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 862
 863   /* We might have new pseudos, so allocate the info arrays for them.  */
 864   if ((debug_new_regalloc & DUMP_SM) == 0)
 865     rtl_dump_file = NULL;
 866   no_new_pseudos = 0;
 867   allocate_reg_info (max_reg_num (), FALSE, FALSE);
 868   no_new_pseudos = 1;
 869   rtl_dump_file = ra_dump_file;
 870
 871   /* Some spill insns could've been inserted after trapping calls, i.e.
 872      at the end of a basic block, which really ends at that call.
 873      Fixup that breakages by adjusting basic block boundaries.  */
 874   fixup_abnormal_edges ();
 875
 876   /* Cleanup the flow graph.  */
 877   if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
 878     rtl_dump_file = NULL;
 879   life_analysis (get_insns (), rtl_dump_file,
 880                  PROP_DEATH_NOTES | PROP_LOG_LINKS  | PROP_REG_INFO);
 881   cleanup_cfg (CLEANUP_EXPENSIVE);
 882   recompute_reg_usage (get_insns (), TRUE);
 883   if (rtl_dump_file)
 884     dump_flow_info (rtl_dump_file);
 885   rtl_dump_file = ra_dump_file;
 886
 887   /* update_equiv_regs() can't be called after register allocation.
 888      It might delete some pseudos, and insert other insns setting
 889      up those pseudos in different places.  This of course screws up
 890      the allocation because that may destroy a hardreg for another
 891      pseudo.
 892      XXX we probably should do something like that on our own.  I.e.
 893      creating REG_EQUIV notes.  */
 894   /*update_equiv_regs ();*/
 895
 896   /* Setup the reg_renumber[] array for reload.  */
 897   setup_renumber (1);
 898   sbitmap_free (insns_with_deaths);
 899
 900   /* Remove REG_DEAD notes which are incorrectly set.  See the docu
 901      of that function.  */
 902   remove_suspicious_death_notes ();
 903
 904   if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
 905     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 906   dump_static_insn_cost (rtl_dump_file,
 907                          "after allocation/spilling, before reload", NULL);
 908
 909   /* Allocate the reg_equiv_memory_loc array for reload.  */
 910   reg_equiv_memory_loc = (rtx *) xcalloc (max_regno, sizeof (rtx));
 911   /* And possibly initialize it.  */
 912   allocate_initial_values (reg_equiv_memory_loc);
 913   /* And one last regclass pass just before reload.  */
 914   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 915 }
 916
 917 /*
 918 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
 919 */