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 = xmalloc ((last_basic_block + 2) * sizeof (bitmap));
 379       for (i = 0; i < last_basic_block + 2; i++)
 380         live_at_end[i] = BITMAP_XMALLOC ();
 381       live_at_end += 2;
 382     }
 383   create_insn_info (df);
 384 }
 385
 386 /* Free the memory which isn't necessary for the next pass.  */
 387
 388 static void
 389 free_mem (df)
 390      struct df *df ATTRIBUTE_UNUSED;
 391 {
 392   free_insn_info ();
 393   ra_build_free ();
 394 }
 395
 396 /* Free all memory allocated for the register allocator.  Used, when
 397    it's done.  */
 398
 399 static void
 400 free_all_mem (df)
 401      struct df *df;
 402 {
 403   unsigned int i;
 404   live_at_end -= 2;
 405   for (i = 0; i < (unsigned)last_basic_block + 2; i++)
 406     BITMAP_XFREE (live_at_end[i]);
 407   free (live_at_end);
 408
 409   ra_colorize_free_all ();
 410   ra_build_free_all (df);
 411   obstack_free (&ra_obstack, NULL);
 412 }
 413
 414 static long ticks_build;
 415 static long ticks_rebuild;
 416
 417 /* Perform one pass of allocation.  Returns nonzero, if some spill code
 418    was added, i.e. if the allocator needs to rerun.  */
 419
 420 static int
 421 one_pass (df, rebuild)
 422      struct df *df;
 423      int rebuild;
 424 {
 425   long ticks = clock ();
 426   int something_spilled;
 427   remember_conflicts = 0;
 428
 429   /* Build the complete interference graph, or if this is not the first
 430      pass, rebuild it incrementally.  */
 431   build_i_graph (df);
 432
 433   /* From now on, if we create new conflicts, we need to remember the
 434      initial list of conflicts per web.  */
 435   remember_conflicts = 1;
 436   if (!rebuild)
 437     dump_igraph_machine ();
 438
 439   /* Colorize the I-graph.  This results in either a list of
 440      spilled_webs, in which case we need to run the spill phase, and
 441      rerun the allocator, or that list is empty, meaning we are done.  */
 442   ra_colorize_graph (df);
 443
 444   last_max_uid = get_max_uid ();
 445   /* actual_spill() might change WEBS(SPILLED) and even empty it,
 446      so we need to remember it's state.  */
 447   something_spilled = !!WEBS(SPILLED);
 448
 449   /* Add spill code if necessary.  */
 450   if (something_spilled)
 451     actual_spill ();
 452
 453   ticks = clock () - ticks;
 454   if (rebuild)
 455     ticks_rebuild += ticks;
 456   else
 457     ticks_build += ticks;
 458   return something_spilled;
 459 }
 460
 461 /* Initialize various arrays for the register allocator.  */
 462
 463 static void
 464 init_ra ()
 465 {
 466   int i;
 467   HARD_REG_SET rs;
 468 #ifdef ELIMINABLE_REGS
 469   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
 470   unsigned int j;
 471 #endif
 472   int need_fp
 473     = (! flag_omit_frame_pointer
 474 #ifdef EXIT_IGNORE_STACK
 475        || (current_function_calls_alloca && EXIT_IGNORE_STACK)
 476 #endif
 477        || FRAME_POINTER_REQUIRED);
 478
 479   ra_colorize_init ();
 480
 481   /* We can't ever use any of the fixed regs.  */
 482   COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
 483
 484   /* Additionally don't even try to use hardregs, which we already
 485      know are not eliminable.  This includes also either the
 486      hard framepointer or all regs which are eliminable into the
 487      stack pointer, if need_fp is set.  */
 488 #ifdef ELIMINABLE_REGS
 489   for (j = 0; j < ARRAY_SIZE (eliminables); j++)
 490     {
 491       if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
 492           || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
 493         for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
 494           SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
 495     }
 496 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 497   if (need_fp)
 498     for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
 499       SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
 500 #endif
 501
 502 #else
 503   if (need_fp)
 504     for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
 505       SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
 506 #endif
 507
 508   /* Stack and argument pointer are also rather useless to us.  */
 509   for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
 510     SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
 511
 512   for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
 513     SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
 514
 515   for (i = 0; i < 256; i++)
 516     {
 517       unsigned char byte = ((unsigned) i) & 0xFF;
 518       unsigned char count = 0;
 519       while (byte)
 520         {
 521           if (byte & 1)
 522             count++;
 523           byte >>= 1;
 524         }
 525       byte2bitcount[i] = count;
 526     }
 527
 528   for (i = 0; i < N_REG_CLASSES; i++)
 529     {
 530       int size;
 531       COPY_HARD_REG_SET (rs, reg_class_contents[i]);
 532       AND_COMPL_HARD_REG_SET (rs, never_use_colors);
 533       size = hard_regs_count (rs);
 534       num_free_regs[i] = size;
 535       COPY_HARD_REG_SET (usable_regs[i], rs);
 536     }
 537
 538   /* Setup hardregs_for_mode[].
 539      We are not interested only in the beginning of a multi-reg, but in
 540      all the hardregs involved.  Maybe HARD_REGNO_MODE_OK() only ok's
 541      for beginnings.  */
 542   for (i = 0; i < NUM_MACHINE_MODES; i++)
 543     {
 544       int reg, size;
 545       CLEAR_HARD_REG_SET (rs);
 546       for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
 547         if (HARD_REGNO_MODE_OK (reg, i)
 548             /* Ignore VOIDmode and similar things.  */
 549             && (size = HARD_REGNO_NREGS (reg, i)) != 0
 550             && (reg + size) <= FIRST_PSEUDO_REGISTER)
 551           {
 552             while (size--)
 553               SET_HARD_REG_BIT (rs, reg + size);
 554           }
 555       COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
 556     }
 557
 558   CLEAR_HARD_REG_SET (invalid_mode_change_regs);
 559 #ifdef CANNOT_CHANGE_MODE_CLASS
 560   if (0)
 561   for (i = 0; i < NUM_MACHINE_MODES; i++)
 562     {
 563       enum machine_mode from = (enum machine_mode) i;
 564       enum machine_mode to;
 565       for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
 566         {
 567           int r;
 568           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 569             if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
 570               SET_HARD_REG_BIT (invalid_mode_change_regs, r);
 571         }
 572     }
 573 #endif
 574
 575   for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
 576        an_unusable_color++)
 577     if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
 578       break;
 579   if (an_unusable_color == FIRST_PSEUDO_REGISTER)
 580     abort ();
 581
 582   orig_max_uid = get_max_uid ();
 583   compute_bb_for_insn ();
 584   ra_reg_renumber = NULL;
 585   insns_with_deaths = sbitmap_alloc (orig_max_uid);
 586   death_insns_max_uid = orig_max_uid;
 587   sbitmap_ones (insns_with_deaths);
 588   gcc_obstack_init (&ra_obstack);
 589 }
 590
 591 /* Check the consistency of DF.  This aborts if it violates some
 592    invariances we expect.  */
 593
 594 static void
 595 check_df (df)
 596      struct df *df;
 597 {
 598   struct df_link *link;
 599   rtx insn;
 600   int regno;
 601   unsigned int ui;
 602   bitmap b = BITMAP_XMALLOC ();
 603   bitmap empty_defs = BITMAP_XMALLOC ();
 604   bitmap empty_uses = BITMAP_XMALLOC ();
 605
 606   /* Collect all the IDs of NULL references in the ID->REF arrays,
 607      as df.c leaves them when updating the df structure.  */
 608   for (ui = 0; ui < df->def_id; ui++)
 609     if (!df->defs[ui])
 610       bitmap_set_bit (empty_defs, ui);
 611   for (ui = 0; ui < df->use_id; ui++)
 612     if (!df->uses[ui])
 613       bitmap_set_bit (empty_uses, ui);
 614
 615   /* For each insn we check if the chain of references contain each
 616      ref only once, doesn't contain NULL refs, or refs whose ID is invalid
 617      (it df->refs[id] element is NULL).  */
 618   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 619     if (INSN_P (insn))
 620       {
 621         bitmap_clear (b);
 622         for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
 623           if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 624               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 625             abort ();
 626           else
 627             bitmap_set_bit (b, DF_REF_ID (link->ref));
 628
 629         bitmap_clear (b);
 630         for (link = DF_INSN_USES (df, insn); link; link = link->next)
 631           if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 632               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 633             abort ();
 634           else
 635             bitmap_set_bit (b, DF_REF_ID (link->ref));
 636       }
 637
 638   /* Now the same for the chains per register number.  */
 639   for (regno = 0; regno < max_reg_num (); regno++)
 640     {
 641       bitmap_clear (b);
 642       for (link = df->regs[regno].defs; link; link = link->next)
 643         if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 644             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 645           abort ();
 646         else
 647           bitmap_set_bit (b, DF_REF_ID (link->ref));
 648
 649       bitmap_clear (b);
 650       for (link = df->regs[regno].uses; link; link = link->next)
 651         if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 652             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 653           abort ();
 654         else
 655           bitmap_set_bit (b, DF_REF_ID (link->ref));
 656     }
 657
 658   BITMAP_XFREE (empty_uses);
 659   BITMAP_XFREE (empty_defs);
 660   BITMAP_XFREE (b);
 661 }
 662
 663 /* Main register allocator entry point.  */
 664
 665 void
 666 reg_alloc ()
 667 {
 668   int changed;
 669   FILE *ra_dump_file = rtl_dump_file;
 670   rtx last = get_last_insn ();
 671
 672   if (! INSN_P (last))
 673     last = prev_real_insn (last);
 674   /* If this is an empty function we shouldn't do all the following,
 675      but instead just setup what's necessary, and return.  */
 676
 677   /* We currently rely on the existence of the return value USE as
 678      one of the last insns.  Add it if it's not there anymore.  */
 679   if (last)
 680     {
 681       edge e;
 682       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 683         {
 684           basic_block bb = e->src;
 685           last = bb->end;
 686           if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
 687             {
 688               rtx insns;
 689               start_sequence ();
 690               use_return_register ();
 691               insns = get_insns ();
 692               end_sequence ();
 693               emit_insn_after (insns, last);
 694             }
 695         }
 696     }
 697
 698   /* Setup debugging levels.  */
 699   switch (0)
 700     {
 701       /* Some useful presets of the debug level, I often use.  */
 702       case 0: debug_new_regalloc = DUMP_EVER; break;
 703       case 1: debug_new_regalloc = DUMP_COSTS; break;
 704       case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
 705       case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
 706       case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
 707               break;
 708       case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
 709               DUMP_CONSTRAINTS;
 710               break;
 711       case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
 712     }
 713   if (!rtl_dump_file)
 714     debug_new_regalloc = 0;
 715
 716   /* Run regclass first, so we know the preferred and alternate classes
 717      for each pseudo.  Deactivate emitting of debug info, if it's not
 718      explicitly requested.  */
 719   if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 720     rtl_dump_file = NULL;
 721   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 722   rtl_dump_file = ra_dump_file;
 723
 724   /* We don't use those NOTEs, and as we anyway change all registers,
 725      they only make problems later.  */
 726   count_or_remove_death_notes (NULL, 1);
 727
 728   /* Initialize the different global arrays and regsets.  */
 729   init_ra ();
 730
 731   /* And some global variables.  */
 732   ra_pass = 0;
 733   no_new_pseudos = 0;
 734   max_normal_pseudo = (unsigned) max_reg_num ();
 735   ra_rewrite_init ();
 736   last_def_id = 0;
 737   last_use_id = 0;
 738   last_num_webs = 0;
 739   last_max_uid = 0;
 740   last_check_uses = NULL;
 741   live_at_end = NULL;
 742   WEBS(INITIAL) = NULL;
 743   WEBS(FREE) = NULL;
 744   memset (hardreg2web, 0, sizeof (hardreg2web));
 745   ticks_build = ticks_rebuild = 0;
 746
 747   /* The default is to use optimistic coalescing with interference
 748      region spilling, without biased coloring.  */
 749   flag_ra_biased = 0;
 750   flag_ra_spill_every_use = 0;
 751   flag_ra_improved_spilling = 1;
 752   flag_ra_ir_spilling = 1;
 753   flag_ra_break_aliases = 0;
 754   flag_ra_optimistic_coalescing = 1;
 755   flag_ra_merge_spill_costs = 1;
 756   if (flag_ra_optimistic_coalescing)
 757     flag_ra_break_aliases = 1;
 758   flag_ra_dump_notes = 0;
 759
 760   /* Allocate the global df structure.  */
 761   df = df_init ();
 762
 763   /* This is the main loop, calling one_pass as long as there are still
 764      some spilled webs.  */
 765   do
 766     {
 767       ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
 768       if (ra_pass++ > 40)
 769         internal_error ("Didn't find a coloring.\n");
 770
 771       /* First collect all the register refs and put them into
 772          chains per insn, and per regno.  In later passes only update
 773          that info from the new and modified insns.  */
 774       df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
 775                   DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
 776
 777       if ((debug_new_regalloc & DUMP_DF) != 0)
 778         {
 779           rtx insn;
 780           df_dump (df, DF_HARD_REGS, rtl_dump_file);
 781           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 782             if (INSN_P (insn))
 783               df_insn_debug_regno (df, insn, rtl_dump_file);
 784         }
 785       check_df (df);
 786
 787       /* Now allocate the memory needed for this pass, or (if it's not the
 788          first pass), reallocate only additional memory.  */
 789       alloc_mem (df);
 790
 791       /* Build and colorize the interference graph, and possibly emit
 792          spill insns.  This also might delete certain move insns.  */
 793       changed = one_pass (df, ra_pass > 1);
 794
 795       /* If that produced no changes, the graph was colorizable.  */
 796       if (!changed)
 797         {
 798           /* Change the insns to refer to the new pseudos (one per web).  */
 799           emit_colors (df);
 800           /* Already setup a preliminary reg_renumber[] array, but don't
 801              free our own version.  reg_renumber[] will again be destroyed
 802              later.  We right now need it in dump_constraints() for
 803              constrain_operands(1) whose subproc sometimes reference
 804              it (because we are checking strictly, i.e. as if
 805              after reload).  */
 806           setup_renumber (0);
 807           /* Delete some more of the coalesced moves.  */
 808           delete_moves ();
 809           dump_constraints ();
 810         }
 811       else
 812         {
 813           /* If there were changes, this means spill code was added,
 814              therefore repeat some things, including some initialization
 815              of global data structures.  */
 816           if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 817             rtl_dump_file = NULL;
 818           /* We have new pseudos (the stackwebs).  */
 819           allocate_reg_info (max_reg_num (), FALSE, FALSE);
 820           /* And new insns.  */
 821           compute_bb_for_insn ();
 822           /* Some of them might be dead.  */
 823           delete_trivially_dead_insns (get_insns (), max_reg_num ());
 824           /* Those new pseudos need to have their REFS count set.  */
 825           reg_scan_update (get_insns (), NULL, max_regno);
 826           max_regno = max_reg_num ();
 827           /* And they need useful classes too.  */
 828           regclass (get_insns (), max_reg_num (), rtl_dump_file);
 829           rtl_dump_file = ra_dump_file;
 830
 831           /* Remember the number of defs and uses, so we can distinguish
 832              new from old refs in the next pass.  */
 833           last_def_id = df->def_id;
 834           last_use_id = df->use_id;
 835         }
 836
 837       /* Output the graph, and possibly the current insn sequence.  */
 838       dump_ra (df);
 839       if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
 840         {
 841           ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 842           fflush (rtl_dump_file);
 843         }
 844
 845       /* Reset the web lists.  */
 846       reset_lists ();
 847       free_mem (df);
 848     }
 849   while (changed);
 850
 851   /* We are done with allocation, free all memory and output some
 852      debug info.  */
 853   free_all_mem (df);
 854   df_finish (df);
 855   if ((debug_new_regalloc & DUMP_RESULTS) == 0)
 856     dump_cost (DUMP_COSTS);
 857   ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
 858   ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
 859   if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
 860     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 861
 862   /* We might have new pseudos, so allocate the info arrays for them.  */
 863   if ((debug_new_regalloc & DUMP_SM) == 0)
 864     rtl_dump_file = NULL;
 865   no_new_pseudos = 0;
 866   allocate_reg_info (max_reg_num (), FALSE, FALSE);
 867   no_new_pseudos = 1;
 868   rtl_dump_file = ra_dump_file;
 869
 870   /* Some spill insns could've been inserted after trapping calls, i.e.
 871      at the end of a basic block, which really ends at that call.
 872      Fixup that breakages by adjusting basic block boundaries.  */
 873   fixup_abnormal_edges ();
 874
 875   /* Cleanup the flow graph.  */
 876   if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
 877     rtl_dump_file = NULL;
 878   life_analysis (get_insns (), rtl_dump_file,
 879                  PROP_DEATH_NOTES | PROP_LOG_LINKS  | PROP_REG_INFO);
 880   cleanup_cfg (CLEANUP_EXPENSIVE);
 881   recompute_reg_usage (get_insns (), TRUE);
 882   if (rtl_dump_file)
 883     dump_flow_info (rtl_dump_file);
 884   rtl_dump_file = ra_dump_file;
 885
 886   /* update_equiv_regs() can't be called after register allocation.
 887      It might delete some pseudos, and insert other insns setting
 888      up those pseudos in different places.  This of course screws up
 889      the allocation because that may destroy a hardreg for another
 890      pseudo.
 891      XXX we probably should do something like that on our own.  I.e.
 892      creating REG_EQUIV notes.  */
 893   /*update_equiv_regs ();*/
 894
 895   /* Setup the reg_renumber[] array for reload.  */
 896   setup_renumber (1);
 897   sbitmap_free (insns_with_deaths);
 898
 899   /* Remove REG_DEAD notes which are incorrectly set.  See the docu
 900      of that function.  */
 901   remove_suspicious_death_notes ();
 902
 903   if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
 904     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 905   dump_static_insn_cost (rtl_dump_file,
 906                          "after allocation/spilling, before reload", NULL);
 907
 908   /* Allocate the reg_equiv_memory_loc array for reload.  */
 909   reg_equiv_memory_loc = xcalloc (max_regno, sizeof (rtx));
 910   /* And possibly initialize it.  */
 911   allocate_initial_values (reg_equiv_memory_loc);
 912   /* And one last regclass pass just before reload.  */
 913   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 914 }
 915
 916 /*
 917 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
 918 */