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