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 unsigned char byte2bitcount[256];
 152
 153 unsigned int debug_new_regalloc = -1;
 154 int flag_ra_biased = 0;
 155 int flag_ra_improved_spilling = 0;
 156 int flag_ra_ir_spilling = 0;
 157 int flag_ra_optimistic_coalescing = 0;
 158 int flag_ra_break_aliases = 0;
 159 int flag_ra_merge_spill_costs = 0;
 160 int flag_ra_spill_every_use = 0;
 161 int flag_ra_dump_notes = 0;
 162
 163 /* Fast allocation of small objects, which live until the allocator
 164    is done.  Allocate an object of SIZE bytes.  */
 165
 166 void *
 167 ra_alloc (size)
 168      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)
 177      size_t size;
 178 {
 179   void *p = obstack_alloc (&ra_obstack, size);
 180   memset (p, 0, size);
 181   return p;
 182 }
 183
 184 /* Returns the number of hardregs in HARD_REG_SET RS.  */
 185
 186 int
 187 hard_regs_count (rs)
 188      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 /* Basically like emit_move_insn (i.e. validifies constants and such),
 218    but also handle MODE_CC moves (but then the operands must already
 219    be basically valid.  */
 220
 221 rtx
 222 ra_emit_move_insn (x, y)
 223      rtx x, y;
 224 {
 225   enum machine_mode mode = GET_MODE (x);
 226   if (GET_MODE_CLASS (mode) == MODE_CC)
 227     return emit_insn (gen_move_insn (x, y));
 228   else
 229     return emit_move_insn (x, y);
 230 }
 231
 232 int insn_df_max_uid;
 233 struct ra_insn_info *insn_df;
 234 static struct ref **refs_for_insn_df;
 235
 236 /* Create the insn_df structure for each insn to have fast access to
 237    all valid defs and uses in an insn.  */
 238
 239 static void
 240 create_insn_info (df)
 241      struct df *df;
 242 {
 243   rtx insn;
 244   struct ref **act_refs;
 245   insn_df_max_uid = get_max_uid ();
 246   insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
 247   refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
 248   act_refs = refs_for_insn_df;
 249   /* We create those things backwards to mimic the order in which
 250      the insns are visited in rewrite_program2() and live_in().  */
 251   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 252     {
 253       int uid = INSN_UID (insn);
 254       unsigned int n;
 255       struct df_link *link;
 256       if (!INSN_P (insn))
 257         continue;
 258       for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
 259         if (link->ref
 260             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 261                 || !TEST_HARD_REG_BIT (never_use_colors,
 262                                        DF_REF_REGNO (link->ref))))
 263           {
 264             if (n == 0)
 265               insn_df[uid].defs = act_refs;
 266             insn_df[uid].defs[n++] = link->ref;
 267           }
 268       act_refs += n;
 269       insn_df[uid].num_defs = n;
 270       for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
 271         if (link->ref
 272             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 273                 || !TEST_HARD_REG_BIT (never_use_colors,
 274                                        DF_REF_REGNO (link->ref))))
 275           {
 276             if (n == 0)
 277               insn_df[uid].uses = act_refs;
 278             insn_df[uid].uses[n++] = link->ref;
 279           }
 280       act_refs += n;
 281       insn_df[uid].num_uses = n;
 282     }
 283   if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
 284     abort ();
 285 }
 286
 287 /* Free the insn_df structures.  */
 288
 289 static void
 290 free_insn_info ()
 291 {
 292   free (refs_for_insn_df);
 293   refs_for_insn_df = NULL;
 294   free (insn_df);
 295   insn_df = NULL;
 296   insn_df_max_uid = 0;
 297 }
 298
 299 /* Search WEB for a subweb, which represents REG.  REG needs to
 300    be a SUBREG, and the inner reg of it needs to be the one which is
 301    represented by WEB.  Returns the matching subweb or NULL.  */
 302
 303 struct web *
 304 find_subweb (web, reg)
 305      struct web *web;
 306      rtx reg;
 307 {
 308   struct web *w;
 309   if (GET_CODE (reg) != SUBREG)
 310     abort ();
 311   for (w = web->subreg_next; w; w = w->subreg_next)
 312     if (GET_MODE (w->orig_x) == GET_MODE (reg)
 313         && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
 314       return w;
 315   return NULL;
 316 }
 317
 318 /* Similar to find_subweb(), but matches according to SIZE_WORD,
 319    a collection of the needed size and offset (in bytes).  */
 320
 321 struct web *
 322 find_subweb_2 (web, size_word)
 323      struct web *web;
 324      unsigned int size_word;
 325 {
 326   struct web *w = web;
 327   if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
 328     /* size_word == size means BYTE_BEGIN(size_word) == 0.  */
 329     return web;
 330   for (w = web->subreg_next; w; w = w->subreg_next)
 331     {
 332       unsigned int bl = rtx_to_bits (w->orig_x);
 333       if (size_word == bl)
 334         return w;
 335     }
 336   return NULL;
 337 }
 338
 339 /* Returns the superweb for SUBWEB.  */
 340
 341 struct web *
 342 find_web_for_subweb_1 (subweb)
 343      struct web *subweb;
 344 {
 345   while (subweb->parent_web)
 346     subweb = subweb->parent_web;
 347   return subweb;
 348 }
 349
 350 /* Determine if two hard register sets intersect.
 351    Return 1 if they do.  */
 352
 353 int
 354 hard_regs_intersect_p (a, b)
 355      HARD_REG_SET *a, *b;
 356 {
 357   HARD_REG_SET c;
 358   COPY_HARD_REG_SET (c, *a);
 359   AND_HARD_REG_SET (c, *b);
 360   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
 361   return 1;
 362 lose:
 363   return 0;
 364 }
 365
 366 /* Allocate and initialize the memory necessary for one pass of the
 367    register allocator.  */
 368
 369 static void
 370 alloc_mem (df)
 371      struct df *df;
 372 {
 373   int i;
 374   ra_build_realloc (df);
 375   if (!live_at_end)
 376     {
 377       live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
 378                                         * 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   for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
 559        an_unusable_color++)
 560     if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
 561       break;
 562   if (an_unusable_color == FIRST_PSEUDO_REGISTER)
 563     abort ();
 564
 565   orig_max_uid = get_max_uid ();
 566   compute_bb_for_insn ();
 567   ra_reg_renumber = NULL;
 568   insns_with_deaths = sbitmap_alloc (orig_max_uid);
 569   death_insns_max_uid = orig_max_uid;
 570   sbitmap_ones (insns_with_deaths);
 571   gcc_obstack_init (&ra_obstack);
 572 }
 573
 574 /* Check the consistency of DF.  This aborts if it violates some
 575    invariances we expect.  */
 576
 577 static void
 578 check_df (df)
 579      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 ()
 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);
 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 = (rtx *) 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 */