gcc/ra.c

   1 /* Graph coloring register allocator
   2    Copyright (C) 2001, 2002, 2003 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 (struct df *);
  89 static void free_insn_info (void);
  90 static void alloc_mem (struct df *);
  91 static void free_mem (struct df *);
  92 static void free_all_mem (struct df *df);
  93 static int one_pass (struct df *, int);
  94 static void check_df (struct df *);
  95 static void init_ra (void);
  96
  97 void reg_alloc (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_t size)
 169 {
 170   return obstack_alloc (&ra_obstack, size);
 171 }
 172
 173 /* Like ra_alloc(), but clear the returned memory.  */
 174
 175 void *
 176 ra_calloc (size_t size)
 177 {
 178   void *p = obstack_alloc (&ra_obstack, size);
 179   memset (p, 0, size);
 180   return p;
 181 }
 182
 183 /* Returns the number of hardregs in HARD_REG_SET RS.  */
 184
 185 int
 186 hard_regs_count (HARD_REG_SET rs)
 187 {
 188   int count = 0;
 189 #ifdef HARD_REG_SET
 190   while (rs)
 191     {
 192       unsigned char byte = rs & 0xFF;
 193       rs >>= 8;
 194       /* Avoid memory access, if nothing is set.  */
 195       if (byte)
 196         count += byte2bitcount[byte];
 197     }
 198 #else
 199   unsigned int ofs;
 200   for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
 201     {
 202       HARD_REG_ELT_TYPE elt = rs[ofs];
 203       while (elt)
 204         {
 205           unsigned char byte = elt & 0xFF;
 206           elt >>= 8;
 207           if (byte)
 208             count += byte2bitcount[byte];
 209         }
 210     }
 211 #endif
 212   return count;
 213 }
 214
 215 /* Basically like emit_move_insn (i.e. validifies constants and such),
 216    but also handle MODE_CC moves (but then the operands must already
 217    be basically valid.  */
 218
 219 rtx
 220 ra_emit_move_insn (rtx x, rtx y)
 221 {
 222   enum machine_mode mode = GET_MODE (x);
 223   if (GET_MODE_CLASS (mode) == MODE_CC)
 224     return emit_insn (gen_move_insn (x, y));
 225   else
 226     return emit_move_insn (x, y);
 227 }
 228
 229 int insn_df_max_uid;
 230 struct ra_insn_info *insn_df;
 231 static struct ref **refs_for_insn_df;
 232
 233 /* Create the insn_df structure for each insn to have fast access to
 234    all valid defs and uses in an insn.  */
 235
 236 static void
 237 create_insn_info (struct df *df)
 238 {
 239   rtx insn;
 240   struct ref **act_refs;
 241   insn_df_max_uid = get_max_uid ();
 242   insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
 243   refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
 244   act_refs = refs_for_insn_df;
 245   /* We create those things backwards to mimic the order in which
 246      the insns are visited in rewrite_program2() and live_in().  */
 247   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 248     {
 249       int uid = INSN_UID (insn);
 250       unsigned int n;
 251       struct df_link *link;
 252       if (!INSN_P (insn))
 253         continue;
 254       for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
 255         if (link->ref
 256             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 257                 || !TEST_HARD_REG_BIT (never_use_colors,
 258                                        DF_REF_REGNO (link->ref))))
 259           {
 260             if (n == 0)
 261               insn_df[uid].defs = act_refs;
 262             insn_df[uid].defs[n++] = link->ref;
 263           }
 264       act_refs += n;
 265       insn_df[uid].num_defs = n;
 266       for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
 267         if (link->ref
 268             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 269                 || !TEST_HARD_REG_BIT (never_use_colors,
 270                                        DF_REF_REGNO (link->ref))))
 271           {
 272             if (n == 0)
 273               insn_df[uid].uses = act_refs;
 274             insn_df[uid].uses[n++] = link->ref;
 275           }
 276       act_refs += n;
 277       insn_df[uid].num_uses = n;
 278     }
 279   if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
 280     abort ();
 281 }
 282
 283 /* Free the insn_df structures.  */
 284
 285 static void
 286 free_insn_info (void)
 287 {
 288   free (refs_for_insn_df);
 289   refs_for_insn_df = NULL;
 290   free (insn_df);
 291   insn_df = NULL;
 292   insn_df_max_uid = 0;
 293 }
 294
 295 /* Search WEB for a subweb, which represents REG.  REG needs to
 296    be a SUBREG, and the inner reg of it needs to be the one which is
 297    represented by WEB.  Returns the matching subweb or NULL.  */
 298
 299 struct web *
 300 find_subweb (struct web *web, rtx reg)
 301 {
 302   struct web *w;
 303   if (GET_CODE (reg) != SUBREG)
 304     abort ();
 305   for (w = web->subreg_next; w; w = w->subreg_next)
 306     if (GET_MODE (w->orig_x) == GET_MODE (reg)
 307         && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
 308       return w;
 309   return NULL;
 310 }
 311
 312 /* Similar to find_subweb(), but matches according to SIZE_WORD,
 313    a collection of the needed size and offset (in bytes).  */
 314
 315 struct web *
 316 find_subweb_2 (struct web *web, unsigned int size_word)
 317 {
 318   struct web *w = web;
 319   if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
 320     /* size_word == size means BYTE_BEGIN(size_word) == 0.  */
 321     return web;
 322   for (w = web->subreg_next; w; w = w->subreg_next)
 323     {
 324       unsigned int bl = rtx_to_bits (w->orig_x);
 325       if (size_word == bl)
 326         return w;
 327     }
 328   return NULL;
 329 }
 330
 331 /* Returns the superweb for SUBWEB.  */
 332
 333 struct web *
 334 find_web_for_subweb_1 (struct web *subweb)
 335 {
 336   while (subweb->parent_web)
 337     subweb = subweb->parent_web;
 338   return subweb;
 339 }
 340
 341 /* Determine if two hard register sets intersect.
 342    Return 1 if they do.  */
 343
 344 int
 345 hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b)
 346 {
 347   HARD_REG_SET c;
 348   COPY_HARD_REG_SET (c, *a);
 349   AND_HARD_REG_SET (c, *b);
 350   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
 351   return 1;
 352 lose:
 353   return 0;
 354 }
 355
 356 /* Allocate and initialize the memory necessary for one pass of the
 357    register allocator.  */
 358
 359 static void
 360 alloc_mem (struct df *df)
 361 {
 362   int i;
 363   ra_build_realloc (df);
 364   if (!live_at_end)
 365     {
 366       live_at_end = xmalloc ((last_basic_block + 2) * sizeof (bitmap));
 367       for (i = 0; i < last_basic_block + 2; i++)
 368         live_at_end[i] = BITMAP_XMALLOC ();
 369       live_at_end += 2;
 370     }
 371   create_insn_info (df);
 372 }
 373
 374 /* Free the memory which isn't necessary for the next pass.  */
 375
 376 static void
 377 free_mem (struct df *df ATTRIBUTE_UNUSED)
 378 {
 379   free_insn_info ();
 380   ra_build_free ();
 381 }
 382
 383 /* Free all memory allocated for the register allocator.  Used, when
 384    it's done.  */
 385
 386 static void
 387 free_all_mem (struct df *df)
 388 {
 389   unsigned int i;
 390   live_at_end -= 2;
 391   for (i = 0; i < (unsigned)last_basic_block + 2; i++)
 392     BITMAP_XFREE (live_at_end[i]);
 393   free (live_at_end);
 394
 395   ra_colorize_free_all ();
 396   ra_build_free_all (df);
 397   obstack_free (&ra_obstack, NULL);
 398 }
 399
 400 static long ticks_build;
 401 static long ticks_rebuild;
 402
 403 /* Perform one pass of allocation.  Returns nonzero, if some spill code
 404    was added, i.e. if the allocator needs to rerun.  */
 405
 406 static int
 407 one_pass (struct df *df, int rebuild)
 408 {
 409   long ticks = clock ();
 410   int something_spilled;
 411   remember_conflicts = 0;
 412
 413   /* Build the complete interference graph, or if this is not the first
 414      pass, rebuild it incrementally.  */
 415   build_i_graph (df);
 416
 417   /* From now on, if we create new conflicts, we need to remember the
 418      initial list of conflicts per web.  */
 419   remember_conflicts = 1;
 420   if (!rebuild)
 421     dump_igraph_machine ();
 422
 423   /* Colorize the I-graph.  This results in either a list of
 424      spilled_webs, in which case we need to run the spill phase, and
 425      rerun the allocator, or that list is empty, meaning we are done.  */
 426   ra_colorize_graph (df);
 427
 428   last_max_uid = get_max_uid ();
 429   /* actual_spill() might change WEBS(SPILLED) and even empty it,
 430      so we need to remember it's state.  */
 431   something_spilled = !!WEBS(SPILLED);
 432
 433   /* Add spill code if necessary.  */
 434   if (something_spilled)
 435     actual_spill ();
 436
 437   ticks = clock () - ticks;
 438   if (rebuild)
 439     ticks_rebuild += ticks;
 440   else
 441     ticks_build += ticks;
 442   return something_spilled;
 443 }
 444
 445 /* Initialize various arrays for the register allocator.  */
 446
 447 static void
 448 init_ra (void)
 449 {
 450   int i;
 451   HARD_REG_SET rs;
 452 #ifdef ELIMINABLE_REGS
 453   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
 454   unsigned int j;
 455 #endif
 456   int need_fp
 457     = (! flag_omit_frame_pointer
 458 #ifdef EXIT_IGNORE_STACK
 459        || (current_function_calls_alloca && EXIT_IGNORE_STACK)
 460 #endif
 461        || FRAME_POINTER_REQUIRED);
 462
 463   ra_colorize_init ();
 464
 465   /* We can't ever use any of the fixed regs.  */
 466   COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
 467
 468   /* Additionally don't even try to use hardregs, which we already
 469      know are not eliminable.  This includes also either the
 470      hard framepointer or all regs which are eliminable into the
 471      stack pointer, if need_fp is set.  */
 472 #ifdef ELIMINABLE_REGS
 473   for (j = 0; j < ARRAY_SIZE (eliminables); j++)
 474     {
 475       if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
 476           || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
 477         for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
 478           SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
 479     }
 480 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 481   if (need_fp)
 482     for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
 483       SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
 484 #endif
 485
 486 #else
 487   if (need_fp)
 488     for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
 489       SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
 490 #endif
 491
 492   /* Stack and argument pointer are also rather useless to us.  */
 493   for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
 494     SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
 495
 496   for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
 497     SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
 498
 499   for (i = 0; i < 256; i++)
 500     {
 501       unsigned char byte = ((unsigned) i) & 0xFF;
 502       unsigned char count = 0;
 503       while (byte)
 504         {
 505           if (byte & 1)
 506             count++;
 507           byte >>= 1;
 508         }
 509       byte2bitcount[i] = count;
 510     }
 511
 512   for (i = 0; i < N_REG_CLASSES; i++)
 513     {
 514       int size;
 515       COPY_HARD_REG_SET (rs, reg_class_contents[i]);
 516       AND_COMPL_HARD_REG_SET (rs, never_use_colors);
 517       size = hard_regs_count (rs);
 518       num_free_regs[i] = size;
 519       COPY_HARD_REG_SET (usable_regs[i], rs);
 520     }
 521
 522   /* Setup hardregs_for_mode[].
 523      We are not interested only in the beginning of a multi-reg, but in
 524      all the hardregs involved.  Maybe HARD_REGNO_MODE_OK() only ok's
 525      for beginnings.  */
 526   for (i = 0; i < NUM_MACHINE_MODES; i++)
 527     {
 528       int reg, size;
 529       CLEAR_HARD_REG_SET (rs);
 530       for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
 531         if (HARD_REGNO_MODE_OK (reg, i)
 532             /* Ignore VOIDmode and similar things.  */
 533             && (size = HARD_REGNO_NREGS (reg, i)) != 0
 534             && (reg + size) <= FIRST_PSEUDO_REGISTER)
 535           {
 536             while (size--)
 537               SET_HARD_REG_BIT (rs, reg + size);
 538           }
 539       COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
 540     }
 541
 542   CLEAR_HARD_REG_SET (invalid_mode_change_regs);
 543 #ifdef CANNOT_CHANGE_MODE_CLASS
 544   if (0)
 545   for (i = 0; i < NUM_MACHINE_MODES; i++)
 546     {
 547       enum machine_mode from = (enum machine_mode) i;
 548       enum machine_mode to;
 549       for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
 550         {
 551           int r;
 552           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 553             if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
 554               SET_HARD_REG_BIT (invalid_mode_change_regs, r);
 555         }
 556     }
 557 #endif
 558
 559   for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
 560        an_unusable_color++)
 561     if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
 562       break;
 563   if (an_unusable_color == FIRST_PSEUDO_REGISTER)
 564     abort ();
 565
 566   orig_max_uid = get_max_uid ();
 567   compute_bb_for_insn ();
 568   ra_reg_renumber = NULL;
 569   insns_with_deaths = sbitmap_alloc (orig_max_uid);
 570   death_insns_max_uid = orig_max_uid;
 571   sbitmap_ones (insns_with_deaths);
 572   gcc_obstack_init (&ra_obstack);
 573 }
 574
 575 /* Check the consistency of DF.  This aborts if it violates some
 576    invariances we expect.  */
 577
 578 static void
 579 check_df (struct df *df)
 580 {
 581   struct df_link *link;
 582   rtx insn;
 583   int regno;
 584   unsigned int ui;
 585   bitmap b = BITMAP_XMALLOC ();
 586   bitmap empty_defs = BITMAP_XMALLOC ();
 587   bitmap empty_uses = BITMAP_XMALLOC ();
 588
 589   /* Collect all the IDs of NULL references in the ID->REF arrays,
 590      as df.c leaves them when updating the df structure.  */
 591   for (ui = 0; ui < df->def_id; ui++)
 592     if (!df->defs[ui])
 593       bitmap_set_bit (empty_defs, ui);
 594   for (ui = 0; ui < df->use_id; ui++)
 595     if (!df->uses[ui])
 596       bitmap_set_bit (empty_uses, ui);
 597
 598   /* For each insn we check if the chain of references contain each
 599      ref only once, doesn't contain NULL refs, or refs whose ID is invalid
 600      (it df->refs[id] element is NULL).  */
 601   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 602     if (INSN_P (insn))
 603       {
 604         bitmap_clear (b);
 605         for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
 606           if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 607               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 608             abort ();
 609           else
 610             bitmap_set_bit (b, DF_REF_ID (link->ref));
 611
 612         bitmap_clear (b);
 613         for (link = DF_INSN_USES (df, insn); link; link = link->next)
 614           if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 615               || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 616             abort ();
 617           else
 618             bitmap_set_bit (b, DF_REF_ID (link->ref));
 619       }
 620
 621   /* Now the same for the chains per register number.  */
 622   for (regno = 0; regno < max_reg_num (); regno++)
 623     {
 624       bitmap_clear (b);
 625       for (link = df->regs[regno].defs; link; link = link->next)
 626         if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
 627             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 628           abort ();
 629         else
 630           bitmap_set_bit (b, DF_REF_ID (link->ref));
 631
 632       bitmap_clear (b);
 633       for (link = df->regs[regno].uses; link; link = link->next)
 634         if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
 635             || bitmap_bit_p (b, DF_REF_ID (link->ref)))
 636           abort ();
 637         else
 638           bitmap_set_bit (b, DF_REF_ID (link->ref));
 639     }
 640
 641   BITMAP_XFREE (empty_uses);
 642   BITMAP_XFREE (empty_defs);
 643   BITMAP_XFREE (b);
 644 }
 645
 646 /* Main register allocator entry point.  */
 647
 648 void
 649 reg_alloc (void)
 650 {
 651   int changed;
 652   FILE *ra_dump_file = rtl_dump_file;
 653   rtx last = get_last_insn ();
 654
 655   if (! INSN_P (last))
 656     last = prev_real_insn (last);
 657   /* If this is an empty function we shouldn't do all the following,
 658      but instead just setup what's necessary, and return.  */
 659
 660   /* We currently rely on the existence of the return value USE as
 661      one of the last insns.  Add it if it's not there anymore.  */
 662   if (last)
 663     {
 664       edge e;
 665       for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 666         {
 667           basic_block bb = e->src;
 668           last = bb->end;
 669           if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
 670             {
 671               rtx insns;
 672               start_sequence ();
 673               use_return_register ();
 674               insns = get_insns ();
 675               end_sequence ();
 676               emit_insn_after (insns, last);
 677             }
 678         }
 679     }
 680
 681   /* Setup debugging levels.  */
 682   switch (0)
 683     {
 684       /* Some useful presets of the debug level, I often use.  */
 685       case 0: debug_new_regalloc = DUMP_EVER; break;
 686       case 1: debug_new_regalloc = DUMP_COSTS; break;
 687       case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
 688       case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
 689       case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
 690               break;
 691       case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
 692               DUMP_CONSTRAINTS;
 693               break;
 694       case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
 695     }
 696   if (!rtl_dump_file)
 697     debug_new_regalloc = 0;
 698
 699   /* Run regclass first, so we know the preferred and alternate classes
 700      for each pseudo.  Deactivate emitting of debug info, if it's not
 701      explicitly requested.  */
 702   if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 703     rtl_dump_file = NULL;
 704   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 705   rtl_dump_file = ra_dump_file;
 706
 707   /* We don't use those NOTEs, and as we anyway change all registers,
 708      they only make problems later.  */
 709   count_or_remove_death_notes (NULL, 1);
 710
 711   /* Initialize the different global arrays and regsets.  */
 712   init_ra ();
 713
 714   /* And some global variables.  */
 715   ra_pass = 0;
 716   no_new_pseudos = 0;
 717   max_normal_pseudo = (unsigned) max_reg_num ();
 718   ra_rewrite_init ();
 719   last_def_id = 0;
 720   last_use_id = 0;
 721   last_num_webs = 0;
 722   last_max_uid = 0;
 723   last_check_uses = NULL;
 724   live_at_end = NULL;
 725   WEBS(INITIAL) = NULL;
 726   WEBS(FREE) = NULL;
 727   memset (hardreg2web, 0, sizeof (hardreg2web));
 728   ticks_build = ticks_rebuild = 0;
 729
 730   /* The default is to use optimistic coalescing with interference
 731      region spilling, without biased coloring.  */
 732   flag_ra_biased = 0;
 733   flag_ra_spill_every_use = 0;
 734   flag_ra_improved_spilling = 1;
 735   flag_ra_ir_spilling = 1;
 736   flag_ra_break_aliases = 0;
 737   flag_ra_optimistic_coalescing = 1;
 738   flag_ra_merge_spill_costs = 1;
 739   if (flag_ra_optimistic_coalescing)
 740     flag_ra_break_aliases = 1;
 741   flag_ra_dump_notes = 0;
 742
 743   /* Allocate the global df structure.  */
 744   df = df_init ();
 745
 746   /* This is the main loop, calling one_pass as long as there are still
 747      some spilled webs.  */
 748   do
 749     {
 750       ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
 751       if (ra_pass++ > 40)
 752         internal_error ("Didn't find a coloring.\n");
 753
 754       /* First collect all the register refs and put them into
 755          chains per insn, and per regno.  In later passes only update
 756          that info from the new and modified insns.  */
 757       df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
 758                   DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
 759
 760       if ((debug_new_regalloc & DUMP_DF) != 0)
 761         {
 762           rtx insn;
 763           df_dump (df, DF_HARD_REGS, rtl_dump_file);
 764           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 765             if (INSN_P (insn))
 766               df_insn_debug_regno (df, insn, rtl_dump_file);
 767         }
 768       check_df (df);
 769
 770       /* Now allocate the memory needed for this pass, or (if it's not the
 771          first pass), reallocate only additional memory.  */
 772       alloc_mem (df);
 773
 774       /* Build and colorize the interference graph, and possibly emit
 775          spill insns.  This also might delete certain move insns.  */
 776       changed = one_pass (df, ra_pass > 1);
 777
 778       /* If that produced no changes, the graph was colorizable.  */
 779       if (!changed)
 780         {
 781           /* Change the insns to refer to the new pseudos (one per web).  */
 782           emit_colors (df);
 783           /* Already setup a preliminary reg_renumber[] array, but don't
 784              free our own version.  reg_renumber[] will again be destroyed
 785              later.  We right now need it in dump_constraints() for
 786              constrain_operands(1) whose subproc sometimes reference
 787              it (because we are checking strictly, i.e. as if
 788              after reload).  */
 789           setup_renumber (0);
 790           /* Delete some more of the coalesced moves.  */
 791           delete_moves ();
 792           dump_constraints ();
 793         }
 794       else
 795         {
 796           /* If there were changes, this means spill code was added,
 797              therefore repeat some things, including some initialization
 798              of global data structures.  */
 799           if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
 800             rtl_dump_file = NULL;
 801           /* We have new pseudos (the stackwebs).  */
 802           allocate_reg_info (max_reg_num (), FALSE, FALSE);
 803           /* And new insns.  */
 804           compute_bb_for_insn ();
 805           /* Some of them might be dead.  */
 806           delete_trivially_dead_insns (get_insns (), max_reg_num ());
 807           /* Those new pseudos need to have their REFS count set.  */
 808           reg_scan_update (get_insns (), NULL, max_regno);
 809           max_regno = max_reg_num ();
 810           /* And they need useful classes too.  */
 811           regclass (get_insns (), max_reg_num (), rtl_dump_file);
 812           rtl_dump_file = ra_dump_file;
 813
 814           /* Remember the number of defs and uses, so we can distinguish
 815              new from old refs in the next pass.  */
 816           last_def_id = df->def_id;
 817           last_use_id = df->use_id;
 818         }
 819
 820       /* Output the graph, and possibly the current insn sequence.  */
 821       dump_ra (df);
 822       if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
 823         {
 824           ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 825           fflush (rtl_dump_file);
 826         }
 827
 828       /* Reset the web lists.  */
 829       reset_lists ();
 830       free_mem (df);
 831     }
 832   while (changed);
 833
 834   /* We are done with allocation, free all memory and output some
 835      debug info.  */
 836   free_all_mem (df);
 837   df_finish (df);
 838   if ((debug_new_regalloc & DUMP_RESULTS) == 0)
 839     dump_cost (DUMP_COSTS);
 840   ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
 841   ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
 842   if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
 843     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 844
 845   /* We might have new pseudos, so allocate the info arrays for them.  */
 846   if ((debug_new_regalloc & DUMP_SM) == 0)
 847     rtl_dump_file = NULL;
 848   no_new_pseudos = 0;
 849   allocate_reg_info (max_reg_num (), FALSE, FALSE);
 850   no_new_pseudos = 1;
 851   rtl_dump_file = ra_dump_file;
 852
 853   /* Some spill insns could've been inserted after trapping calls, i.e.
 854      at the end of a basic block, which really ends at that call.
 855      Fixup that breakages by adjusting basic block boundaries.  */
 856   fixup_abnormal_edges ();
 857
 858   /* Cleanup the flow graph.  */
 859   if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
 860     rtl_dump_file = NULL;
 861   life_analysis (get_insns (), rtl_dump_file,
 862                  PROP_DEATH_NOTES | PROP_LOG_LINKS  | PROP_REG_INFO);
 863   cleanup_cfg (CLEANUP_EXPENSIVE);
 864   recompute_reg_usage (get_insns (), TRUE);
 865   if (rtl_dump_file)
 866     dump_flow_info (rtl_dump_file);
 867   rtl_dump_file = ra_dump_file;
 868
 869   /* update_equiv_regs() can't be called after register allocation.
 870      It might delete some pseudos, and insert other insns setting
 871      up those pseudos in different places.  This of course screws up
 872      the allocation because that may destroy a hardreg for another
 873      pseudo.
 874      XXX we probably should do something like that on our own.  I.e.
 875      creating REG_EQUIV notes.  */
 876   /*update_equiv_regs ();*/
 877
 878   /* Setup the reg_renumber[] array for reload.  */
 879   setup_renumber (1);
 880   sbitmap_free (insns_with_deaths);
 881
 882   /* Remove REG_DEAD notes which are incorrectly set.  See the docu
 883      of that function.  */
 884   remove_suspicious_death_notes ();
 885
 886   if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
 887     ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
 888   dump_static_insn_cost (rtl_dump_file,
 889                          "after allocation/spilling, before reload", NULL);
 890
 891   /* Allocate the reg_equiv_memory_loc array for reload.  */
 892   reg_equiv_memory_loc = xcalloc (max_regno, sizeof (rtx));
 893   /* And possibly initialize it.  */
 894   allocate_initial_values (reg_equiv_memory_loc);
 895   /* And one last regclass pass just before reload.  */
 896   regclass (get_insns (), max_reg_num (), rtl_dump_file);
 897 }
 898
 899 /*
 900 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
 901 */