contrib/gcc-3.4/gcc/ra.c

   1 /* Graph coloring register allocator
   2    Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Michael Matz <matz@suse.de>
   4    and Daniel Berlin <dan@cgsoftware.com>.
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify it under the
   9    terms of the GNU General Public License as published by the Free Software
  10    Foundation; either version 2, or (at your option) any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  15    details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with GCC; see the file COPYING.  If not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tm_p.h"
  27 #include "insn-config.h"
  28 #include "recog.h"
  29 #include "reload.h"
  30 #include "integrate.h"
  31 #include "function.h"
  32 #include "regs.h"
  33 #include "obstack.h"
  34 #include "hard-reg-set.h"
  35 #include "basic-block.h"
  36 #include "df.h"
  37 #include "expr.h"
  38 #include "output.h"
  39 #include "toplev.h"
  40 #include "flags.h"
  41 #include "ra.h"
  42
  43 /* This is the toplevel file of a graph coloring register allocator.
  44    It is able to act like a George & Appel allocator, i.e. with iterative
  45    coalescing plus spill coalescing/propagation.
  46    And it can act as a traditional Briggs allocator, although with
  47    optimistic coalescing.  Additionally it has a custom pass, which
  48    tries to reduce the overall cost of the colored graph.
  49
  50    We support two modes of spilling: spill-everywhere, which is extremely
  51    fast, and interference region spilling, which reduces spill code to a
  52    large extent, but is slower.
  53
  54    Helpful documents:
  55
  56    Briggs, P., Cooper, K. D., and Torczon, L. 1994. Improvements to graph
  57    coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May),
  58    428-455.
  59
  60    Bergner, P., Dahl, P., Engebretsen, D., and O'Keefe, M. 1997. Spill code
  61    minimization via interference region spilling. In Proc. ACM SIGPLAN '97
  62    Conf. on Prog. Language Design and Implementation. ACM, 287-295.
  63
  64    George, L., Appel, A.W. 1996.  Iterated register coalescing.
  65    ACM Trans. Program. Lang. Syst. 18, 3 (May), 300-324.
  66
  67 */
  68
  69 /* This file contains the main entry point (reg_alloc), some helper routines
  70    used by more than one file of the register allocator, and the toplevel
  71    driver procedure (one_pass).  */
  72
  73 /* Things, one might do somewhen:
  74
  75    * Lattice based rematerialization
  76    * create definitions of ever-life regs at the beginning of
  77      the insn chain
  78    * insert loads as soon, stores as late as possible
  79    * insert spill insns as outward as possible (either looptree, or LCM)
  80    * reuse stack-slots
  81    * delete coalesced insns.  Partly done.  The rest can only go, when we get
  82      rid of reload.
  83    * don't destroy coalescing information completely when spilling
  84    * use the constraints from asms
  85   */
  86
  87 static struct obstack ra_obstack;
  88 static void create_insn_info (struct df *);
  89 static void free_insn_info (void);
  90 static void alloc_mem (struct df *);
  91 static void free_mem (struct df *);
  92 static void free_all_mem (struct df *df);
  93 static int one_pass (struct df *, int);
  94 static void check_df (struct df *);
  95 static void init_ra (void);
  96
  97 void reg_alloc (void);
  98
  99 /* These global variables are "internal" to the register allocator.
 100    They are all documented at their declarations in ra.h.  */
 101
 102 /* Somewhen we want to get rid of one of those sbitmaps.
 103    (for now I need the sup_igraph to note if there is any conflict between
 104    parts of webs at all.  I can't use igraph for this, as there only the real
 105    conflicts are noted.)  This is only used to prevent coalescing two
 106    conflicting webs, were only parts of them are in conflict.  */
 107 sbitmap igraph;
 108 sbitmap sup_igraph;
 109
 110 /* Note the insns not inserted by the allocator, where we detected any
 111    deaths of pseudos.  It is used to detect closeness of defs and uses.
 112    In the first pass this is empty (we could initialize it from REG_DEAD
 113    notes), in the other passes it is left from the pass before.  */
 114 sbitmap insns_with_deaths;
 115 int death_insns_max_uid;
 116
 117 struct web_part *web_parts;
 118
 119 unsigned int num_webs;
 120 unsigned int num_subwebs;
 121 unsigned int num_allwebs;
 122 struct web **id2web;
 123 struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
 124 struct web **def2web;
 125 struct web **use2web;
 126 struct move_list *wl_moves;
 127 int ra_max_regno;
 128 short *ra_reg_renumber;
 129 struct df *df;
 130 bitmap *live_at_end;
 131 int ra_pass;
 132 unsigned int max_normal_pseudo;
 133 int an_unusable_color;
 134
 135 /* The different lists on which a web can be (based on the type).  */
 136 struct dlist *web_lists[(int) LAST_NODE_TYPE];
 137
 138 unsigned int last_def_id;
 139 unsigned int last_use_id;
 140 unsigned int last_num_webs;
 141 int last_max_uid;
 142 sbitmap last_check_uses;
 143 unsigned int remember_conflicts;
 144
 145 int orig_max_uid;
 146
 147 HARD_REG_SET never_use_colors;
 148 HARD_REG_SET usable_regs[N_REG_CLASSES];
 149 unsigned int num_free_regs[N_REG_CLASSES];
 150 HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
 151 HARD_REG_SET invalid_mode_change_regs;
 152 unsigned char byte2bitcount[256];
 153
 154 unsigned int debug_new_regalloc = -1;
 155 int flag_ra_biased = 0;
 156 int flag_ra_improved_spilling = 0;
 157 int flag_ra_ir_spilling = 0;
 158 int flag_ra_optimistic_coalescing = 0;
 159 int flag_ra_break_aliases = 0;
 160 int flag_ra_merge_spill_costs = 0;
 161 int flag_ra_spill_every_use = 0;
 162 int flag_ra_dump_notes = 0;
 163
 164 /* Fast allocation of small objects, which live until the allocator
 165    is done.  Allocate an object of SIZE bytes.  */
 166
 167 void *
 168 ra_alloc (size_t size)
 169 {
 170   return obstack_alloc (&ra_obstack, size);
 171 }
 172
 173 /* Like ra_alloc(), but clear the returned memory.  */
 174
 175 void *
 176 ra_calloc (size_t size)
 177 {
 178   void *p = obstack_alloc (&ra_obstack, size);
 179   memset (p, 0, size);
 180   return p;
 181 }
 182
 183 /* Returns the number of hardregs in HARD_REG_SET RS.  */
 184
 185 int
 186 hard_regs_count (HARD_REG_SET rs)
 187 {
 188   int count = 0;
 189 #ifdef HARD_REG_SET
 190   while (rs)
 191     {
 192       unsigned char byte = rs & 0xFF;
 193       rs >>= 8;
 194       /* Avoid memory access, if nothing is set.  */
 195       if (byte)
 196         count += byte2bitcount[byte];
 197     }
 198 #else
 199   unsigned int ofs;
 200   for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
 201     {
 202       HARD_REG_ELT_TYPE elt = rs[ofs];
 203       while (elt)
 204         {
 205           unsigned char byte = elt & 0xFF;
 206           elt >>= 8;
 207           if (byte)
 208             count += byte2bitcount[byte];
 209         }
 210     }
 211 #endif
 212   return count;
 213 }
 214
 215 /* Basically like emit_move_insn (i.e. validifies constants and such),
 216    but also handle MODE_CC moves (but then the operands must already
 217    be basically valid.  */
 218
 219 rtx
 220 ra_emit_move_insn (rtx x, rtx y)
 221 {
 222   enum machine_mode mode = GET_MODE (x);
 223   if (GET_MODE_CLASS (mode) == MODE_CC)
 224     return emit_insn (gen_move_insn (x, y));
 225   else
 226     return emit_move_insn (x, y);
 227 }
 228
 229 int insn_df_max_uid;
 230 struct ra_insn_info *insn_df;
 231 static struct ref **refs_for_insn_df;
 232
 233 /* Create the insn_df structure for each insn to have fast access to
 234    all valid defs and uses in an insn.  */
 235
 236 static void
 237 create_insn_info (struct df *df)
 238 {
 239   rtx insn;
 240   struct ref **act_refs;
 241   insn_df_max_uid = get_max_uid ();
 242   insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
 243   refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
 244   act_refs = refs_for_insn_df;
 245   /* We create those things backwards to mimic the order in which
 246      the insns are visited in rewrite_program2() and live_in().  */
 247   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 248     {
 249       int uid = INSN_UID (insn);
 250       unsigned int n;
 251       struct df_link *link;
 252       if (!INSN_P (insn))
 253         continue;
 254       for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
 255         if (link->ref
 256             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 257                 || !TEST_HARD_REG_BIT (never_use_colors,
 258                                        DF_REF_REGNO (link->ref))))
 259           {
 260             if (n == 0)
 261               insn_df[uid].defs = act_refs;
 262             insn_df[uid].defs[n++] = link->ref;
 263           }
 264       act_refs += n;
 265       insn_df[uid].num_defs = n;
 266       for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
 267         if (link->ref
 268             && (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
 269                 || !TEST_HARD_REG_BIT (never_use_colors,
 270                                        DF_REF_REGNO (link->ref))))
 271           {
 272             if (n == 0)
 273               insn_df[uid].uses = act_refs;
 274             insn_df[uid].uses[n++] = link->ref;
 275           }
 276       act_refs += n;
 277       insn_df[uid].num_uses = n;
 278     }
 279   if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
 280     abort ();
 281 }
 282
 283 /* Free the insn_df structures.  */
 284
 285 static void
 286 free_insn_info (void)
 287 {
 288   free (refs_for_insn_df);
 289   refs_for_insn_df = NULL;
 290   free (insn_df);
 291   insn_df = NULL;
 292   insn_df_max_uid = 0;
 293 }
 294
 295 /* Search WEB for a subweb, which represents REG.  REG needs to
 296    be a SUBREG, and the inner reg of it needs to be the one which is
 297    represented by WEB.  Returns the matching subweb or NULL.  */
 298
 299 struct web *
 300 find_subweb (struct web *web, rtx reg)
 301 {
 302   struct web *w;
 303   if (GET_CODE (reg) != SUBREG)
 304     abort ();
 305   for (w = web->subreg_next; w; w = w->subreg_next)
 306     if (GET_MODE (w->orig_x) == GET_MODE (reg)
 307         && SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
 308       return w;
 309   return NULL;
 310 }
 311
 312 /* Similar to find_subweb(), but matches according to SIZE_WORD,
 313    a collection of the needed size and offset (in bytes).  */
 314
 315 struct web *
 316 find_subweb_2 (struct web *web, unsigned int size_word)
 317 {
 318   struct web *w = web;
 319   if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
 320     /* size_word == size means BYTE_BEGIN(size_word) == 0.  */
 321     return web;
 322   for (w = web->subreg_next; w; w = w->subreg_next)
 323     {
 324       unsigned int bl = rtx_to_bits (w->orig_x);
 325       if (size_word == bl)
 326         return w;
 327     }
 328   return NULL;
 329 }
 330
 331 /* Returns the superweb for SUBWEB.  */
 332
 333 struct web *
 334 find_web_for_subweb_1 (struct web *subweb)
 335 {
 336   while (subweb->parent_web)
 337     subweb = subweb->parent_web;
 338   return subweb;
 339 }
 340
 341 /* Determine if two hard register sets intersect.
 342    Return 1 if they do.  */
 343
 344 int
 345 hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b)
 346 {
 347   HARD_REG_SET c;
 348   COPY_HARD_REG_SET (c, *a);
 349   AND_HARD_REG_SET (c, *b);
 350   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
 351   return 1;
 352 lose:
 353   return 0;
 354 }
 355
 356 /* Allocate and initialize the memory necessary for one pass of the
 357    register allocator.  */
 358
 359 static void
 360 alloc_mem (struct df *df)
 361 {
 362   int i;
 363   ra_build_realloc (df);
 364   if (!live_at_end)
 365     {
 366       live_at_end = xmalloc ((last_basic_block + 2) * sizeof (bitmap));
 367       for (i = 0; i < last_basic_block + 2; i++)
 368         live_at_end[i] = BITMAP_XMALLOC ();
 369       live_at_end += 2;
 370     }
 371   create_insn_info (df);
 372 }
 373
 374 /* Free the memory which isn't necessary for the next pass.  */
 375
 376 static void
 377 free_mem (struct df *df ATTRIBUTE_UNUSED)
 378 {
 379   free_insn_info ();
 380   ra_build_free ();
 381 }
 382
 383 /* Free all memory allocated for the register allocator.  Used, when
 384    it's done.  */
 385
 386 static void
 387 free_all_mem (struct df *df)
 388 {
 389   unsigned int i;
 390   live_at_end -= 2;
 391   for (i = 0; i < (unsigned)last_basic_block + 2; i++)
 392     BITMAP_XFREE (live_at_end[i]);
 393   free (live_at_end);
 394
 395   ra_colorize_free_all ();
 396   ra_build_free_all (df);
 397   obstack_free (&ra_obstack, NULL);
 398 }
 399
 400 static long ticks_build;
 401 static long ticks_rebuild;
 402
 403 /* Perform one pass of allocation.  Returns nonzero, if some spill code
 404    was added, i.e. if the allocator needs to rerun.  */
 405
 406 static int
 407 one_pass (struct df *df, int rebuild)
 408 {
 409   long ticks = clock ();
 410   int something_spilled;
 411   remember_conflicts = 0;
 412
 413   /* Build the complete interference graph, or if this is not the first
 414      pass, rebuild it incrementally.  */
 415   build_i_graph (df);
 416
 417   /* From now on, if we create new conflicts, we need to remember the
 418      initial list of conflicts per web.  */
 419   remember_conflicts = 1;
 420   if (!rebuild)
 421     dump_igraph_machine ();
 422
 423   /* Colorize the I-graph.  This results in either a list of
 424      spilled_webs, in which case we need to run the spill phase, and
 425      rerun the allocator, or that list is empty, meaning we are done.  */
 426   ra_colorize_graph (df);
 427
 428   last_max_uid = get_max_uid ();
 429   /* actual_spill() might change WEBS(SPILLED) and even empty it,
 430      so we need to remember it's state.  */
 431   something_spilled = !!WEBS(SPILLED);
 432
 433   /* Add spill code if necessary.  */
 434   if (something_spilled)
 435     actual_spill ();
 436
 437   ticks = clock () - ticks;
 438   if (rebuild)
 439     ticks_rebuild += ticks;
 440   else
 441     ticks_build += ticks;
 442   return something_spilled;
 443 }
 444
 445 /* Initialize various arrays for the register allocator.  */
 446
 447 static void
 448 init_ra (void)
 449 {
 450   int i;
 451   HARD_REG_SET rs;
 452 #ifdef ELIMINABLE_REGS
 453   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
 454   unsigned int j;
 455 #endif
 456   int need_fp
 457     = (! flag_omit_frame_pointer
 458        || (current_function_calls_alloca && EXIT_IGNORE_STACK)
 459        || FRAME_POINTER_REQUIRED);
 460
 461   ra_colorize_init ();
 462
 463   /* We can't ever use any of the fixed regs.  */
 464   COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
 465
 466   /* Additionally don't even try to use hardregs, which we already
 467      know are not eliminable.  This includes also either the
 468      hard framepointer or all regs which are eliminable into the
 469      stack pointer, if need_fp is set.  */
 470 #ifdef ELIMINABLE_REGS
 471   for (j = 0; j < ARRAY_SIZE (eliminables); j++)
 472     {
 473       if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
 474           || (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
 475         for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
 476           SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
 477     }
 478 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 479   if (need_fp)
 480     for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
 481       SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
 482 #endif
 483
 484 #else
 485   if (need_fp)
 486     for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
 487       SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
 488 #endif
 489
 490   /* Stack and argument pointer are also rather useless to us.  */
 491   for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
 492     SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
 493
 494   for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
 495     SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
 496
 497   for (i = 0; i < 256; i++)
 498     {
 499       unsigned char byte = ((unsigned) i) & 0xFF;
 500       unsigned char count = 0;
 501       while (byte)
 502         {
 503           if (byte & 1)
 504             count++;
 505           byte >>= 1;
 506         }
 507       byte2bitcount[i] = count;
 508     }
 509
 510   for (i = 0; i < N_REG_CLASSES; i++)
 511     {
 512       int size;
 513       COPY_HARD_REG_SET (rs, reg_class_contents[i]);
 514       AND_COMPL_HARD_REG_SET (rs, never_use_colors);
 515       size = hard_regs_count (rs);
 516       num_free_regs[i] = size;
 517       COPY_HARD_REG_SET (usable_regs[i], rs);
 518     }
 519
 520   /* Setup hardregs_for_mode[].
 521      We are not interested only in the beginning of a multi-reg, but in
 522      all the hardregs involved.  Maybe HARD_REGNO_MODE_OK() only ok's
 523      for beginnings.  */
 524   for (i = 0; i < NUM_MACHINE_MODES; i++)
 525     {
 526       int reg, size;
 527       CLEAR_HARD_REG_SET (rs);
 528       for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
 529         if (HARD_REGNO_MODE_OK (reg, i)
 530             /* Ignore VOIDmode and similar things.  */
 531             && (size = HARD_REGNO_NREGS (reg, i)) != 0
 532             && (reg + size) <= FIRST_PSEUDO_REGISTER)
 533           {
 534             while (size--)
 535               SET_HARD_REG_BIT (rs, reg + size);
 536           }
 537       COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
 538     }
 539
 540   CLEAR_HARD_REG_SET (invalid_mode_change_regs);
 541 #ifdef CANNOT_CHANGE_MODE_CLASS
 542   if (0)
 543   for (i = 0; i < NUM_MACHINE_MODES; i++)
 544     {
 545       enum machine_mode from = (enum machine_mode) i;
 546       enum machine_mode to;
 547       for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
 548         {
 549           int r;
 550           for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
 551             if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
 552               SET_HARD_REG_BIT (invalid_mode_change_regs, r);
 553         }
 554     }
 555 #endif
 556
 557   for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
 558        an_unusable_color++)
 559     if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
 560       break;
 561   if (an_unusable_color == FIRST_PSEUDO_REGISTER)
 562     abort ();
 563
 564   orig_max_uid = get_max_uid ();
 565   compute_bb_for_insn ();
 566   ra_reg_renumber = NULL;
 567   insns_with_deaths = sbitmap_alloc (orig_max_uid);
 568   death_insns_max_uid = orig_max_uid;
 569   sbitmap_ones (insns_with_deaths);
 570   gcc_obstack_init (&ra_obstack);
 571 }
 572
 573 /* Check the consistency of DF.  This aborts if it violates some
 574    invariances we expect.  */
 575
 576 static void
 577 check_df (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 (void)
 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 existence 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 (bb);
 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 useful 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      explicitly 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 | DF_FOR_REGALLOC);
 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 useful 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 = 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 */