gcc/ra.c

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