gcc/ra-colorize.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 "function.h"
  28 #include "regs.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "df.h"
  32 #include "output.h"
  33 #include "ra.h"
  34
  35 /* This file is part of the graph coloring register allocator.
  36    It contains the graph colorizer.  Given an interference graph
  37    as set up in ra-build.c the toplevel function in this file
  38    (ra_colorize_graph) colorizes the graph, leaving a list
  39    of colored, coalesced and spilled nodes.
  40
  41    The algorithm used is a merge of George & Appels iterative coalescing
  42    and optimistic coalescing, switchable at runtime.  The current default
  43    is "optimistic coalescing +", which is based on the normal Briggs/Cooper
  44    framework.  We can also use biased coloring.  Most of the structure
  45    here follows the different papers.
  46
  47    Additionally there is a custom step to locally improve the overall
  48    spill cost of the colored graph (recolor_spills).  */
  49
  50 static void push_list PARAMS ((struct dlist *, struct dlist **));
  51 static void push_list_end PARAMS ((struct dlist *, struct dlist **));
  52 static void free_dlist PARAMS ((struct dlist **));
  53 static void put_web_at_end PARAMS ((struct web *, enum node_type));
  54 static void put_move PARAMS ((struct move *, enum move_type));
  55 static void build_worklists PARAMS ((struct df *));
  56 static void enable_move PARAMS ((struct web *));
  57 static void decrement_degree PARAMS ((struct web *, int));
  58 static void simplify PARAMS ((void));
  59 static void remove_move_1 PARAMS ((struct web *, struct move *));
  60 static void remove_move PARAMS ((struct web *, struct move *));
  61 static void add_worklist PARAMS ((struct web *));
  62 static int ok PARAMS ((struct web *, struct web *));
  63 static int conservative PARAMS ((struct web *, struct web *));
  64 static inline unsigned int simplify_p PARAMS ((enum node_type));
  65 static void combine PARAMS ((struct web *, struct web *));
  66 static void coalesce PARAMS ((void));
  67 static void freeze_moves PARAMS ((struct web *));
  68 static void freeze PARAMS ((void));
  69 static void select_spill PARAMS ((void));
  70 static int color_usable_p PARAMS ((int, HARD_REG_SET, HARD_REG_SET,
  71                                    enum machine_mode));
  72 int get_free_reg PARAMS ((HARD_REG_SET, HARD_REG_SET, enum machine_mode));
  73 static int get_biased_reg PARAMS ((HARD_REG_SET, HARD_REG_SET, HARD_REG_SET,
  74                                    HARD_REG_SET, enum machine_mode));
  75 static int count_long_blocks PARAMS ((HARD_REG_SET, int));
  76 static char * hardregset_to_string PARAMS ((HARD_REG_SET));
  77 static void calculate_dont_begin PARAMS ((struct web *, HARD_REG_SET *));
  78 static void colorize_one_web PARAMS ((struct web *, int));
  79 static void assign_colors PARAMS ((void));
  80 static void try_recolor_web PARAMS ((struct web *));
  81 static void insert_coalesced_conflicts PARAMS ((void));
  82 static int comp_webs_maxcost PARAMS ((const void *, const void *));
  83 static void recolor_spills PARAMS ((void));
  84 static void check_colors PARAMS ((void));
  85 static void restore_conflicts_from_coalesce PARAMS ((struct web *));
  86 static void break_coalesced_spills PARAMS ((void));
  87 static void unalias_web PARAMS ((struct web *));
  88 static void break_aliases_to_web PARAMS ((struct web *));
  89 static void break_precolored_alias PARAMS ((struct web *));
  90 static void init_web_pairs PARAMS ((void));
  91 static void add_web_pair_cost PARAMS ((struct web *, struct web *,
  92                                        unsigned HOST_WIDE_INT, unsigned int));
  93 static int comp_web_pairs PARAMS ((const void *, const void *));
  94 static void sort_and_combine_web_pairs PARAMS ((int));
  95 static void aggressive_coalesce PARAMS ((void));
  96 static void extended_coalesce_2 PARAMS ((void));
  97 static void check_uncoalesced_moves PARAMS ((void));
  98
  99 static struct dlist *mv_worklist, *mv_coalesced, *mv_constrained;
 100 static struct dlist *mv_frozen, *mv_active;
 101
 102 /* Push a node onto the front of the list.  */
 103
 104 static void
 105 push_list (x, list)
 106      struct dlist *x;
 107      struct dlist **list;
 108 {
 109   if (x->next || x->prev)
 110     abort ();
 111   x->next = *list;
 112   if (*list)
 113     (*list)->prev = x;
 114   *list = x;
 115 }
 116
 117 static void
 118 push_list_end (x, list)
 119      struct dlist *x;
 120      struct dlist **list;
 121 {
 122   if (x->prev || x->next)
 123     abort ();
 124   if (!*list)
 125     {
 126       *list = x;
 127       return;
 128     }
 129   while ((*list)->next)
 130     list = &((*list)->next);
 131   x->prev = *list;
 132   (*list)->next = x;
 133 }
 134
 135 /* Remove a node from the list.  */
 136
 137 void
 138 remove_list (x, list)
 139      struct dlist *x;
 140      struct dlist **list;
 141 {
 142   struct dlist *y = x->prev;
 143   if (y)
 144     y->next = x->next;
 145   else
 146     *list = x->next;
 147   y = x->next;
 148   if (y)
 149     y->prev = x->prev;
 150   x->next = x->prev = NULL;
 151 }
 152
 153 /* Pop the front of the list.  */
 154
 155 struct dlist *
 156 pop_list (list)
 157      struct dlist **list;
 158 {
 159   struct dlist *r = *list;
 160   if (r)
 161     remove_list (r, list);
 162   return r;
 163 }
 164
 165 /* Free the given double linked list.  */
 166
 167 static void
 168 free_dlist (list)
 169      struct dlist **list;
 170 {
 171   *list = NULL;
 172 }
 173
 174 /* The web WEB should get the given new TYPE.  Put it onto the
 175    appropriate list.
 176    Inline, because it's called with constant TYPE every time.  */
 177
 178 inline void
 179 put_web (web, type)
 180      struct web *web;
 181      enum node_type type;
 182 {
 183   switch (type)
 184     {
 185       case INITIAL:
 186       case FREE:
 187       case FREEZE:
 188       case SPILL:
 189       case SPILLED:
 190       case COALESCED:
 191       case COLORED:
 192       case SELECT:
 193         push_list (web->dlink, &WEBS(type));
 194         break;
 195       case PRECOLORED:
 196         push_list (web->dlink, &WEBS(INITIAL));
 197         break;
 198       case SIMPLIFY:
 199         if (web->spill_temp)
 200           push_list (web->dlink, &WEBS(type = SIMPLIFY_SPILL));
 201         else if (web->add_hardregs)
 202           push_list (web->dlink, &WEBS(type = SIMPLIFY_FAT));
 203         else
 204           push_list (web->dlink, &WEBS(SIMPLIFY));
 205         break;
 206       default:
 207         abort ();
 208     }
 209   web->type = type;
 210 }
 211
 212 /* After we are done with the whole pass of coloring/spilling,
 213    we reset the lists of webs, in preparation of the next pass.
 214    The spilled webs become free, colored webs go to the initial list,
 215    coalesced webs become free or initial, according to what type of web
 216    they are coalesced to.  */
 217
 218 void
 219 reset_lists ()
 220 {
 221   struct dlist *d;
 222   unsigned int i;
 223   if (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_SPILL) || WEBS(SIMPLIFY_FAT)
 224       || WEBS(FREEZE) || WEBS(SPILL) || WEBS(SELECT))
 225     abort ();
 226
 227   while ((d = pop_list (&WEBS(COALESCED))) != NULL)
 228     {
 229       struct web *web = DLIST_WEB (d);
 230       struct web *aweb = alias (web);
 231       /* Note, how alias() becomes invalid through the two put_web()'s
 232          below.  It might set the type of a web to FREE (from COALESCED),
 233          which itself is a target of aliasing (i.e. in the middle of
 234          an alias chain).  We can handle this by checking also for
 235          type == FREE.  Note nevertheless, that alias() is invalid
 236          henceforth.  */
 237       if (aweb->type == SPILLED || aweb->type == FREE)
 238         put_web (web, FREE);
 239       else
 240         put_web (web, INITIAL);
 241     }
 242   while ((d = pop_list (&WEBS(SPILLED))) != NULL)
 243     put_web (DLIST_WEB (d), FREE);
 244   while ((d = pop_list (&WEBS(COLORED))) != NULL)
 245     put_web (DLIST_WEB (d), INITIAL);
 246
 247   /* All free webs have no conflicts anymore.  */
 248   for (d = WEBS(FREE); d; d = d->next)
 249     {
 250       struct web *web = DLIST_WEB (d);
 251       BITMAP_XFREE (web->useless_conflicts);
 252       web->useless_conflicts = NULL;
 253     }
 254
 255   /* Sanity check, that we only have free, initial or precolored webs.  */
 256   for (i = 0; i < num_webs; i++)
 257     {
 258       struct web *web = ID2WEB (i);
 259       if (web->type != INITIAL && web->type != FREE && web->type != PRECOLORED)
 260         abort ();
 261     }
 262   free_dlist (&mv_worklist);
 263   free_dlist (&mv_coalesced);
 264   free_dlist (&mv_constrained);
 265   free_dlist (&mv_frozen);
 266   free_dlist (&mv_active);
 267 }
 268
 269 /* Similar to put_web(), but add the web to the end of the appropriate
 270    list.  Additionally TYPE may not be SIMPLIFY.  */
 271
 272 static void
 273 put_web_at_end (web, type)
 274      struct web *web;
 275      enum node_type type;
 276 {
 277   if (type == PRECOLORED)
 278     type = INITIAL;
 279   else if (type == SIMPLIFY)
 280     abort ();
 281   push_list_end (web->dlink, &WEBS(type));
 282   web->type = type;
 283 }
 284
 285 /* Unlink WEB from the list it's currently on (which corresponds to
 286    its current type).  */
 287
 288 void
 289 remove_web_from_list (web)
 290      struct web *web;
 291 {
 292   if (web->type == PRECOLORED)
 293     remove_list (web->dlink, &WEBS(INITIAL));
 294   else
 295     remove_list (web->dlink, &WEBS(web->type));
 296 }
 297
 298 /* Give MOVE the TYPE, and link it into the correct list.  */
 299
 300 static inline void
 301 put_move (move, type)
 302      struct move *move;
 303      enum move_type type;
 304 {
 305   switch (type)
 306     {
 307       case WORKLIST:
 308         push_list (move->dlink, &mv_worklist);
 309         break;
 310       case MV_COALESCED:
 311         push_list (move->dlink, &mv_coalesced);
 312         break;
 313       case CONSTRAINED:
 314         push_list (move->dlink, &mv_constrained);
 315         break;
 316       case FROZEN:
 317         push_list (move->dlink, &mv_frozen);
 318         break;
 319       case ACTIVE:
 320         push_list (move->dlink, &mv_active);
 321         break;
 322       default:
 323         abort ();
 324     }
 325   move->type = type;
 326 }
 327
 328 /* Build the worklists we are going to process.  */
 329
 330 static void
 331 build_worklists (df)
 332      struct df *df ATTRIBUTE_UNUSED;
 333 {
 334   struct dlist *d, *d_next;
 335   struct move_list *ml;
 336
 337   /* If we are not the first pass, put all stackwebs (which are still
 338      backed by a new pseudo, but conceptually can stand for a stackslot,
 339      i.e. it doesn't really matter if they get a color or not), on
 340      the SELECT stack first, those with lowest cost first.  This way
 341      they will be colored last, so do not constrain the coloring of the
 342      normal webs.  But still those with the highest count are colored
 343      before, i.e. get a color more probable.  The use of stackregs is
 344      a pure optimization, and all would work, if we used real stackslots
 345      from the begin.  */
 346   if (ra_pass > 1)
 347     {
 348       unsigned int i, num, max_num;
 349       struct web **order2web;
 350       max_num = num_webs - num_subwebs;
 351       order2web = (struct web **) xmalloc (max_num * sizeof (order2web[0]));
 352       for (i = 0, num = 0; i < max_num; i++)
 353         if (id2web[i]->regno >= max_normal_pseudo)
 354           order2web[num++] = id2web[i];
 355       if (num)
 356         {
 357           qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
 358           for (i = num - 1;; i--)
 359             {
 360               struct web *web = order2web[i];
 361               struct conflict_link *wl;
 362               remove_list (web->dlink, &WEBS(INITIAL));
 363               put_web (web, SELECT);
 364               for (wl = web->conflict_list; wl; wl = wl->next)
 365                 {
 366                   struct web *pweb = wl->t;
 367                   pweb->num_conflicts -= 1 + web->add_hardregs;
 368                 }
 369               if (i == 0)
 370                 break;
 371             }
 372         }
 373       free (order2web);
 374     }
 375
 376   /* For all remaining initial webs, classify them.  */
 377   for (d = WEBS(INITIAL); d; d = d_next)
 378     {
 379       struct web *web = DLIST_WEB (d);
 380       d_next = d->next;
 381       if (web->type == PRECOLORED)
 382         continue;
 383
 384       remove_list (d, &WEBS(INITIAL));
 385       if (web->num_conflicts >= NUM_REGS (web))
 386         put_web (web, SPILL);
 387       else if (web->moves)
 388         put_web (web, FREEZE);
 389       else
 390         put_web (web, SIMPLIFY);
 391     }
 392
 393   /* And put all moves on the worklist for iterated coalescing.
 394      Note, that if iterated coalescing is off, then wl_moves doesn't
 395      contain any moves.  */
 396   for (ml = wl_moves; ml; ml = ml->next)
 397     if (ml->move)
 398       {
 399         struct move *m = ml->move;
 400         d = (struct dlist *) ra_calloc (sizeof (struct dlist));
 401         DLIST_MOVE (d) = m;
 402         m->dlink = d;
 403         put_move (m, WORKLIST);
 404       }
 405 }
 406
 407 /* Enable the active moves, in which WEB takes part, to be processed.  */
 408
 409 static void
 410 enable_move (web)
 411      struct web *web;
 412 {
 413   struct move_list *ml;
 414   for (ml = web->moves; ml; ml = ml->next)
 415     if (ml->move->type == ACTIVE)
 416       {
 417         remove_list (ml->move->dlink, &mv_active);
 418         put_move (ml->move, WORKLIST);
 419       }
 420 }
 421
 422 /* Decrement the degree of node WEB by the amount DEC.
 423    Possibly change the type of WEB, if the number of conflicts is
 424    now smaller than its freedom.  */
 425
 426 static void
 427 decrement_degree (web, dec)
 428      struct web *web;
 429      int dec;
 430 {
 431   int before = web->num_conflicts;
 432   web->num_conflicts -= dec;
 433   if (web->num_conflicts < NUM_REGS (web) && before >= NUM_REGS (web))
 434     {
 435       struct conflict_link *a;
 436       enable_move (web);
 437       for (a = web->conflict_list; a; a = a->next)
 438         {
 439           struct web *aweb = a->t;
 440           if (aweb->type != SELECT && aweb->type != COALESCED)
 441             enable_move (aweb);
 442         }
 443       if (web->type != FREEZE)
 444         {
 445           remove_web_from_list (web);
 446           if (web->moves)
 447             put_web (web, FREEZE);
 448           else
 449             put_web (web, SIMPLIFY);
 450         }
 451     }
 452 }
 453
 454 /* Repeatedly simplify the nodes on the simplify worklists.  */
 455
 456 static void
 457 simplify ()
 458 {
 459   struct dlist *d;
 460   struct web *web;
 461   struct conflict_link *wl;
 462   while (1)
 463     {
 464       /* We try hard to color all the webs resulting from spills first.
 465          Without that on register starved machines (x86 e.g) with some live
 466          DImode pseudos, -fPIC, and an asm requiring %edx, it might be, that
 467          we do rounds over rounds, because the conflict graph says, we can
 468          simplify those short webs, but later due to irregularities we can't
 469          color those pseudos.  So we have to spill them, which in later rounds
 470          leads to other spills.  */
 471       d = pop_list (&WEBS(SIMPLIFY));
 472       if (!d)
 473         d = pop_list (&WEBS(SIMPLIFY_FAT));
 474       if (!d)
 475         d = pop_list (&WEBS(SIMPLIFY_SPILL));
 476       if (!d)
 477         break;
 478       web = DLIST_WEB (d);
 479       ra_debug_msg (DUMP_PROCESS, " simplifying web %3d, conflicts = %d\n",
 480                  web->id, web->num_conflicts);
 481       put_web (web, SELECT);
 482       for (wl = web->conflict_list; wl; wl = wl->next)
 483         {
 484           struct web *pweb = wl->t;
 485           if (pweb->type != SELECT && pweb->type != COALESCED)
 486             {
 487               decrement_degree (pweb, 1 + web->add_hardregs);
 488             }
 489         }
 490     }
 491 }
 492
 493 /* Helper function to remove a move from the movelist of the web.  */
 494
 495 static void
 496 remove_move_1 (web, move)
 497      struct web *web;
 498      struct move *move;
 499 {
 500   struct move_list *ml = web->moves;
 501   if (!ml)
 502     return;
 503   if (ml->move == move)
 504     {
 505       web->moves = ml->next;
 506       return;
 507     }
 508   for (; ml->next && ml->next->move != move; ml = ml->next) ;
 509   if (!ml->next)
 510     return;
 511   ml->next = ml->next->next;
 512 }
 513
 514 /* Remove a move from the movelist of the web.  Actually this is just a
 515    wrapper around remove_move_1(), making sure, the removed move really is
 516    not in the list anymore.  */
 517
 518 static void
 519 remove_move (web, move)
 520      struct web *web;
 521      struct move *move;
 522 {
 523   struct move_list *ml;
 524   remove_move_1 (web, move);
 525   for (ml = web->moves; ml; ml = ml->next)
 526     if (ml->move == move)
 527       abort ();
 528 }
 529
 530 /* Merge the moves for the two webs into the first web's movelist.  */
 531
 532 void
 533 merge_moves (u, v)
 534      struct web *u, *v;
 535 {
 536   regset seen;
 537   struct move_list *ml;
 538
 539   seen = BITMAP_XMALLOC ();
 540   for (ml = u->moves; ml; ml = ml->next)
 541     bitmap_set_bit (seen, INSN_UID (ml->move->insn));
 542   for (ml = v->moves; ml; ml = ml->next)
 543     {
 544       if (! bitmap_bit_p (seen, INSN_UID (ml->move->insn)))
 545         {
 546           ml->next = u->moves;
 547           u->moves = ml;
 548         }
 549     }
 550   BITMAP_XFREE (seen);
 551   v->moves = NULL;
 552 }
 553
 554 /* Add a web to the simplify worklist, from the freeze worklist.  */
 555
 556 static void
 557 add_worklist (web)
 558      struct web *web;
 559 {
 560   if (web->type != PRECOLORED && !web->moves
 561       && web->num_conflicts < NUM_REGS (web))
 562     {
 563       remove_list (web->dlink, &WEBS(FREEZE));
 564       put_web (web, SIMPLIFY);
 565     }
 566 }
 567
 568 /* Precolored node coalescing heuristic.  */
 569
 570 static int
 571 ok (target, source)
 572      struct web *target, *source;
 573 {
 574   struct conflict_link *wl;
 575   int i;
 576   int color = source->color;
 577   int size;
 578
 579   /* Normally one would think, the next test wouldn't be needed.
 580      We try to coalesce S and T, and S has already a color, and we checked
 581      when processing the insns, that both have the same mode.  So naively
 582      we could conclude, that of course that mode was valid for this color.
 583      Hah.  But there is sparc.  Before reload there are copy insns
 584      (e.g. the ones copying arguments to locals) which happily refer to
 585      colors in invalid modes.  We can't coalesce those things.  */
 586   if (! HARD_REGNO_MODE_OK (source->color, GET_MODE (target->orig_x)))
 587     return 0;
 588
 589   /* Sanity for funny modes.  */
 590   size = HARD_REGNO_NREGS (color, GET_MODE (target->orig_x));
 591   if (!size)
 592     return 0;
 593
 594   /* We can't coalesce target with a precolored register which isn't in
 595      usable_regs.  */
 596   for (i = size; i--;)
 597     if (TEST_HARD_REG_BIT (never_use_colors, color + i)
 598         || !TEST_HARD_REG_BIT (target->usable_regs, color + i)
 599         /* Before usually calling ok() at all, we already test, if the
 600            candidates conflict in sup_igraph.  But when wide webs are
 601            coalesced to hardregs, we only test the hardweb coalesced into.
 602            This is only the begin color.  When actually coalescing both,
 603            it will also take the following size colors, i.e. their webs.
 604            We nowhere checked if the candidate possibly conflicts with
 605            one of _those_, which is possible with partial conflicts,
 606            so we simply do it here (this does one bit-test more than
 607            necessary, the first color).  Note, that if X is precolored
 608            bit [X*num_webs + Y] can't be set (see add_conflict_edge()).  */
 609         || TEST_BIT (sup_igraph,
 610                      target->id * num_webs + hardreg2web[color + i]->id))
 611       return 0;
 612
 613   for (wl = target->conflict_list; wl; wl = wl->next)
 614     {
 615       struct web *pweb = wl->t;
 616       if (pweb->type == SELECT || pweb->type == COALESCED)
 617         continue;
 618
 619       /* Coalescing target (T) and source (S) is o.k, if for
 620          all conflicts C of T it is true, that:
 621           1) C will be colored, or
 622           2) C is a hardreg (precolored), or
 623           3) C already conflicts with S too, or
 624           4) a web which contains C conflicts already with S.
 625          XXX: we handle here only the special case of 4), that C is
 626          a subreg, and the containing thing is the reg itself, i.e.
 627          we dont handle the situation, were T conflicts with
 628          (subreg:SI x 1), and S conflicts with (subreg:DI x 0), which
 629          would be allowed also, as the S-conflict overlaps
 630          the T-conflict.
 631          So, we first test the whole web for any of these conditions, and
 632          continue with the next C, if 1, 2 or 3 is true.  */
 633       if (pweb->num_conflicts < NUM_REGS (pweb)
 634           || pweb->type == PRECOLORED
 635           || TEST_BIT (igraph, igraph_index (source->id, pweb->id)) )
 636         continue;
 637
 638       /* This is reached, if not one of 1, 2 or 3 was true.  In the case C has
 639          no subwebs, 4 can't be true either, so we can't coalesce S and T.  */
 640       if (wl->sub == NULL)
 641         return 0;
 642       else
 643         {
 644           /* The main webs do _not_ conflict, only some parts of both.  This
 645              means, that 4 is possibly true, so we need to check this too.
 646              For this we go thru all sub conflicts between T and C, and see if
 647              the target part of C already conflicts with S.  When this is not
 648              the case we disallow coalescing.  */
 649           struct sub_conflict *sl;
 650           for (sl = wl->sub; sl; sl = sl->next)
 651             {
 652               if (!TEST_BIT (igraph, igraph_index (source->id, sl->t->id)))
 653                 return 0;
 654             }
 655         }
 656     }
 657   return 1;
 658 }
 659
 660 /* Non-precolored node coalescing heuristic.  */
 661
 662 static int
 663 conservative (target, source)
 664      struct web *target, *source;
 665 {
 666   unsigned int k;
 667   unsigned int loop;
 668   regset seen;
 669   struct conflict_link *wl;
 670   unsigned int num_regs = NUM_REGS (target); /* XXX */
 671
 672   /* k counts the resulting conflict weight, if target and source
 673      would be merged, and all low-degree neighbors would be
 674      removed.  */
 675   k = 0 * MAX (target->add_hardregs, source->add_hardregs);
 676   seen = BITMAP_XMALLOC ();
 677   for (loop = 0; loop < 2; loop++)
 678     for (wl = ((loop == 0) ? target : source)->conflict_list;
 679          wl; wl = wl->next)
 680       {
 681         struct web *pweb = wl->t;
 682         if (pweb->type != SELECT && pweb->type != COALESCED
 683             && pweb->num_conflicts >= NUM_REGS (pweb)
 684             && ! REGNO_REG_SET_P (seen, pweb->id))
 685           {
 686             SET_REGNO_REG_SET (seen, pweb->id);
 687             k += 1 + pweb->add_hardregs;
 688           }
 689       }
 690   BITMAP_XFREE (seen);
 691
 692   if (k >= num_regs)
 693     return 0;
 694   return 1;
 695 }
 696
 697 /* If the web is coalesced, return it's alias.  Otherwise, return what
 698    was passed in.  */
 699
 700 struct web *
 701 alias (web)
 702      struct web *web;
 703 {
 704   while (web->type == COALESCED)
 705     web = web->alias;
 706   return web;
 707 }
 708
 709 /* Returns nonzero, if the TYPE belongs to one of those representing
 710    SIMPLIFY types.  */
 711
 712 static inline unsigned int
 713 simplify_p (type)
 714      enum node_type type;
 715 {
 716   return type == SIMPLIFY || type == SIMPLIFY_SPILL || type == SIMPLIFY_FAT;
 717 }
 718
 719 /* Actually combine two webs, that can be coalesced.  */
 720
 721 static void
 722 combine (u, v)
 723      struct web *u, *v;
 724 {
 725   int i;
 726   struct conflict_link *wl;
 727   if (u == v || v->type == COALESCED)
 728     abort ();
 729   if ((u->regno >= max_normal_pseudo) != (v->regno >= max_normal_pseudo))
 730     abort ();
 731   remove_web_from_list (v);
 732   put_web (v, COALESCED);
 733   v->alias = u;
 734   u->is_coalesced = 1;
 735   v->is_coalesced = 1;
 736   u->num_aliased += 1 + v->num_aliased;
 737   if (flag_ra_merge_spill_costs && u->type != PRECOLORED)
 738     u->spill_cost += v->spill_cost;
 739     /*u->spill_cost = MAX (u->spill_cost, v->spill_cost);*/
 740   merge_moves (u, v);
 741   /* combine add_hardregs's of U and V.  */
 742
 743   for (wl = v->conflict_list; wl; wl = wl->next)
 744     {
 745       struct web *pweb = wl->t;
 746       /* We don't strictly need to move conflicts between webs which are
 747          already coalesced or selected, if we do iterated coalescing, or
 748          better if we need not to be able to break aliases again.
 749          I.e. normally we would use the condition
 750          (pweb->type != SELECT && pweb->type != COALESCED).
 751          But for now we simply merge all conflicts.  It doesn't take that
 752          much time.  */
 753       if (1)
 754         {
 755           struct web *web = u;
 756           int nregs = 1 + v->add_hardregs;
 757           if (u->type == PRECOLORED)
 758             nregs = HARD_REGNO_NREGS (u->color, GET_MODE (v->orig_x));
 759
 760           /* For precolored U's we need to make conflicts between V's
 761              neighbors and as many hardregs from U as V needed if it gets
 762              color U.  For now we approximate this by V->add_hardregs, which
 763              could be too much in multi-length classes.  We should really
 764              count how many hardregs are needed for V with color U.  When U
 765              isn't precolored this loop breaks out after one iteration.  */
 766           for (i = 0; i < nregs; i++)
 767             {
 768               if (u->type == PRECOLORED)
 769                 web = hardreg2web[i + u->color];
 770               if (wl->sub == NULL)
 771                 record_conflict (web, pweb);
 772               else
 773                 {
 774                   struct sub_conflict *sl;
 775                   /* So, between V and PWEB there are sub_conflicts.  We
 776                      need to relocate those conflicts to be between WEB (==
 777                      U when it wasn't precolored) and PWEB.  In the case
 778                      only a part of V conflicted with (part of) PWEB we
 779                      nevertheless make the new conflict between the whole U
 780                      and the (part of) PWEB.  Later we might try to find in
 781                      U the correct subpart corresponding (by size and
 782                      offset) to the part of V (sl->s) which was the source
 783                      of the conflict.  */
 784                   for (sl = wl->sub; sl; sl = sl->next)
 785                     {
 786                       /* Beware: sl->s is no subweb of web (== U) but of V.
 787                          We try to search a corresponding subpart of U.
 788                          If we found none we let it conflict with the whole U.
 789                          Note that find_subweb() only looks for mode and
 790                          subreg_byte of the REG rtx but not for the pseudo
 791                          reg number (otherwise it would be guaranteed to
 792                          _not_ find any subpart).  */
 793                       struct web *sweb = NULL;
 794                       if (SUBWEB_P (sl->s))
 795                         sweb = find_subweb (web, sl->s->orig_x);
 796                       if (!sweb)
 797                         sweb = web;
 798                       record_conflict (sweb, sl->t);
 799                     }
 800                 }
 801               if (u->type != PRECOLORED)
 802                 break;
 803             }
 804           if (pweb->type != SELECT && pweb->type != COALESCED)
 805             decrement_degree (pweb, 1 + v->add_hardregs);
 806         }
 807     }
 808
 809   /* Now merge the usable_regs together.  */
 810   /* XXX That merging might normally make it necessary to
 811      adjust add_hardregs, which also means to adjust neighbors.  This can
 812      result in making some more webs trivially colorable, (or the opposite,
 813      if this increases our add_hardregs).  Because we intersect the
 814      usable_regs it should only be possible to decrease add_hardregs.  So a
 815      conservative solution for now is to simply don't change it.  */
 816   u->use_my_regs = 1;
 817   AND_HARD_REG_SET (u->usable_regs, v->usable_regs);
 818   u->regclass = reg_class_subunion[u->regclass][v->regclass];
 819   /* Count number of possible hardregs.  This might make U a spillweb,
 820      but that could also happen, if U and V together had too many
 821      conflicts.  */
 822   u->num_freedom = hard_regs_count (u->usable_regs);
 823   u->num_freedom -= u->add_hardregs;
 824   /* The next would mean an invalid coalesced move (both webs have no
 825      possible hardreg in common), so abort.  */
 826   if (!u->num_freedom)
 827     abort();
 828
 829   if (u->num_conflicts >= NUM_REGS (u)
 830       && (u->type == FREEZE || simplify_p (u->type)))
 831     {
 832       remove_web_from_list (u);
 833       put_web (u, SPILL);
 834     }
 835
 836   /* We want the most relaxed combination of spill_temp state.
 837      I.e. if any was no spilltemp or a spilltemp2, the result is so too,
 838      otherwise if any is short, the result is too.  It remains, when both
 839      are normal spilltemps.  */
 840   if (v->spill_temp == 0)
 841     u->spill_temp = 0;
 842   else if (v->spill_temp == 2 && u->spill_temp != 0)
 843     u->spill_temp = 2;
 844   else if (v->spill_temp == 3 && u->spill_temp == 1)
 845     u->spill_temp = 3;
 846 }
 847
 848 /* Attempt to coalesce the first thing on the move worklist.
 849    This is used only for iterated coalescing.  */
 850
 851 static void
 852 coalesce ()
 853 {
 854   struct dlist *d = pop_list (&mv_worklist);
 855   struct move *m = DLIST_MOVE (d);
 856   struct web *source = alias (m->source_web);
 857   struct web *target = alias (m->target_web);
 858
 859   if (target->type == PRECOLORED)
 860     {
 861       struct web *h = source;
 862       source = target;
 863       target = h;
 864     }
 865   if (source == target)
 866     {
 867       remove_move (source, m);
 868       put_move (m, MV_COALESCED);
 869       add_worklist (source);
 870     }
 871   else if (target->type == PRECOLORED
 872            || TEST_BIT (sup_igraph, source->id * num_webs + target->id)
 873            || TEST_BIT (sup_igraph, target->id * num_webs + source->id))
 874     {
 875       remove_move (source, m);
 876       remove_move (target, m);
 877       put_move (m, CONSTRAINED);
 878       add_worklist (source);
 879       add_worklist (target);
 880     }
 881   else if ((source->type == PRECOLORED && ok (target, source))
 882            || (source->type != PRECOLORED
 883                && conservative (target, source)))
 884     {
 885       remove_move (source, m);
 886       remove_move (target, m);
 887       put_move (m, MV_COALESCED);
 888       combine (source, target);
 889       add_worklist (source);
 890     }
 891   else
 892     put_move (m, ACTIVE);
 893 }
 894
 895 /* Freeze the moves associated with the web.  Used for iterated coalescing.  */
 896
 897 static void
 898 freeze_moves (web)
 899      struct web *web;
 900 {
 901   struct move_list *ml, *ml_next;
 902   for (ml = web->moves; ml; ml = ml_next)
 903     {
 904       struct move *m = ml->move;
 905       struct web *src, *dest;
 906       ml_next = ml->next;
 907       if (m->type == ACTIVE)
 908         remove_list (m->dlink, &mv_active);
 909       else
 910         remove_list (m->dlink, &mv_worklist);
 911       put_move (m, FROZEN);
 912       remove_move (web, m);
 913       src = alias (m->source_web);
 914       dest = alias (m->target_web);
 915       src = (src == web) ? dest : src;
 916       remove_move (src, m);
 917       /* XXX GA use the original v, instead of alias(v) */
 918       if (!src->moves && src->num_conflicts < NUM_REGS (src))
 919         {
 920           remove_list (src->dlink, &WEBS(FREEZE));
 921           put_web (src, SIMPLIFY);
 922         }
 923     }
 924 }
 925
 926 /* Freeze the first thing on the freeze worklist (only for iterated
 927    coalescing).  */
 928
 929 static void
 930 freeze ()
 931 {
 932   struct dlist *d = pop_list (&WEBS(FREEZE));
 933   put_web (DLIST_WEB (d), SIMPLIFY);
 934   freeze_moves (DLIST_WEB (d));
 935 }
 936
 937 /* The current spill heuristic.  Returns a number for a WEB.
 938    Webs with higher numbers are selected later.  */
 939
 940 static unsigned HOST_WIDE_INT (*spill_heuristic) PARAMS ((struct web *));
 941
 942 static unsigned HOST_WIDE_INT default_spill_heuristic PARAMS ((struct web *));
 943
 944 /* Our default heuristic is similar to spill_cost / num_conflicts.
 945    Just scaled for integer arithmetic, and it favors coalesced webs,
 946    and webs which span more insns with deaths.  */
 947
 948 static unsigned HOST_WIDE_INT
 949 default_spill_heuristic (web)
 950      struct web *web;
 951 {
 952   unsigned HOST_WIDE_INT ret;
 953   unsigned int divisor = 1;
 954   /* Make coalesce targets cheaper to spill, because they will be broken
 955      up again into smaller parts.  */
 956   if (flag_ra_break_aliases)
 957     divisor += web->num_aliased;
 958   divisor += web->num_conflicts;
 959   ret = ((web->spill_cost << 8) + divisor - 1) / divisor;
 960   /* It is better to spill webs that span more insns (deaths in our
 961      case) than other webs with the otherwise same spill_cost.  So make
 962      them a little bit cheaper.  Remember that spill_cost is unsigned.  */
 963   if (web->span_deaths < ret)
 964     ret -= web->span_deaths;
 965   return ret;
 966 }
 967
 968 /* Select the cheapest spill to be potentially spilled (we don't
 969    *actually* spill until we need to).  */
 970
 971 static void
 972 select_spill ()
 973 {
 974   unsigned HOST_WIDE_INT best = (unsigned HOST_WIDE_INT) -1;
 975   struct dlist *bestd = NULL;
 976   unsigned HOST_WIDE_INT best2 = (unsigned HOST_WIDE_INT) -1;
 977   struct dlist *bestd2 = NULL;
 978   struct dlist *d;
 979   for (d = WEBS(SPILL); d; d = d->next)
 980     {
 981       struct web *w = DLIST_WEB (d);
 982       unsigned HOST_WIDE_INT cost = spill_heuristic (w);
 983       if ((!w->spill_temp) && cost < best)
 984         {
 985           best = cost;
 986           bestd = d;
 987         }
 988       /* Specially marked spill temps can be spilled.  Also coalesce
 989          targets can.  Eventually they will be broken up later in the
 990          colorizing process, so if we have nothing better take that.  */
 991       else if ((w->spill_temp == 2 || w->is_coalesced) && cost < best2)
 992         {
 993           best2 = cost;
 994           bestd2 = d;
 995         }
 996     }
 997   if (!bestd)
 998     {
 999       bestd = bestd2;
1000       best = best2;
1001     }
1002   if (!bestd)
1003     abort ();
1004
1005   /* Note the potential spill.  */
1006   DLIST_WEB (bestd)->was_spilled = 1;
1007   remove_list (bestd, &WEBS(SPILL));
1008   put_web (DLIST_WEB (bestd), SIMPLIFY);
1009   freeze_moves (DLIST_WEB (bestd));
1010   ra_debug_msg (DUMP_PROCESS, " potential spill web %3d, conflicts = %d\n",
1011              DLIST_WEB (bestd)->id, DLIST_WEB (bestd)->num_conflicts);
1012 }
1013
1014 /* Given a set of forbidden colors to begin at, and a set of still
1015    free colors, and MODE, returns nonzero of color C is still usable.  */
1016
1017 static int
1018 color_usable_p (c, dont_begin_colors, free_colors, mode)
1019      int c;
1020      HARD_REG_SET dont_begin_colors, free_colors;
1021      enum machine_mode mode;
1022 {
1023   if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
1024       && TEST_HARD_REG_BIT (free_colors, c)
1025       && HARD_REGNO_MODE_OK (c, mode))
1026     {
1027       int i, size;
1028       size = HARD_REGNO_NREGS (c, mode);
1029       for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
1030       if (i == size)
1031         return 1;
1032     }
1033   return 0;
1034 }
1035
1036 /* I don't want to clutter up the actual code with ifdef's.  */
1037 #ifdef REG_ALLOC_ORDER
1038 #define INV_REG_ALLOC_ORDER(c) inv_reg_alloc_order[c]
1039 #else
1040 #define INV_REG_ALLOC_ORDER(c) c
1041 #endif
1042
1043 /* Searches in FREE_COLORS for a block of hardregs of the right length
1044    for MODE, which doesn't begin at a hardreg mentioned in DONT_BEGIN_COLORS.
1045    If it needs more than one hardreg it prefers blocks beginning
1046    at an even hardreg, and only gives an odd begin reg if no other
1047    block could be found.  */
1048
1049 int
1050 get_free_reg (dont_begin_colors, free_colors, mode)
1051      HARD_REG_SET dont_begin_colors, free_colors;
1052      enum machine_mode mode;
1053 {
1054   int c;
1055   int last_resort_reg = -1;
1056   int pref_reg = -1;
1057   int pref_reg_order = INT_MAX;
1058   int last_resort_reg_order = INT_MAX;
1059
1060   for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1061     if (!TEST_HARD_REG_BIT (dont_begin_colors, c)
1062         && TEST_HARD_REG_BIT (free_colors, c)
1063         && HARD_REGNO_MODE_OK (c, mode))
1064       {
1065         int i, size;
1066         size = HARD_REGNO_NREGS (c, mode);
1067         for (i = 1; i < size && TEST_HARD_REG_BIT (free_colors, c + i); i++);
1068         if (i != size)
1069           {
1070             c += i;
1071             continue;
1072           }
1073         if (i == size)
1074           {
1075             if (size < 2 || (c & 1) == 0)
1076               {
1077                 if (INV_REG_ALLOC_ORDER (c) < pref_reg_order)
1078                   {
1079                     pref_reg = c;
1080                     pref_reg_order = INV_REG_ALLOC_ORDER (c);
1081                   }
1082               }
1083             else if (INV_REG_ALLOC_ORDER (c) < last_resort_reg_order)
1084               {
1085                 last_resort_reg = c;
1086                 last_resort_reg_order = INV_REG_ALLOC_ORDER (c);
1087               }
1088           }
1089         else
1090           c += i;
1091       }
1092   return pref_reg >= 0 ? pref_reg : last_resort_reg;
1093 }
1094
1095 /* Similar to get_free_reg(), but first search in colors provided
1096    by BIAS _and_ PREFER_COLORS, then in BIAS alone, then in PREFER_COLORS
1097    alone, and only then for any free color.  If flag_ra_biased is zero
1098    only do the last two steps.  */
1099
1100 static int
1101 get_biased_reg (dont_begin_colors, bias, prefer_colors, free_colors, mode)
1102      HARD_REG_SET dont_begin_colors, bias, prefer_colors, free_colors;
1103      enum machine_mode mode;
1104 {
1105   int c = -1;
1106   HARD_REG_SET s;
1107   if (flag_ra_biased)
1108     {
1109       COPY_HARD_REG_SET (s, dont_begin_colors);
1110       IOR_COMPL_HARD_REG_SET (s, bias);
1111       IOR_COMPL_HARD_REG_SET (s, prefer_colors);
1112       c = get_free_reg (s, free_colors, mode);
1113       if (c >= 0)
1114         return c;
1115       COPY_HARD_REG_SET (s, dont_begin_colors);
1116       IOR_COMPL_HARD_REG_SET (s, bias);
1117       c = get_free_reg (s, free_colors, mode);
1118       if (c >= 0)
1119         return c;
1120     }
1121   COPY_HARD_REG_SET (s, dont_begin_colors);
1122   IOR_COMPL_HARD_REG_SET (s, prefer_colors);
1123   c = get_free_reg (s, free_colors, mode);
1124   if (c >= 0)
1125       return c;
1126   c = get_free_reg (dont_begin_colors, free_colors, mode);
1127   return c;
1128 }
1129
1130 /* Counts the number of non-overlapping bitblocks of length LEN
1131    in FREE_COLORS.  */
1132
1133 static int
1134 count_long_blocks (free_colors, len)
1135      HARD_REG_SET free_colors;
1136      int len;
1137 {
1138   int i, j;
1139   int count = 0;
1140   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1141     {
1142       if (!TEST_HARD_REG_BIT (free_colors, i))
1143         continue;
1144       for (j = 1; j < len; j++)
1145         if (!TEST_HARD_REG_BIT (free_colors, i + j))
1146           break;
1147       /* Bits [i .. i+j-1] are free.  */
1148       if (j == len)
1149         count++;
1150       i += j - 1;
1151     }
1152   return count;
1153 }
1154
1155 /* Given a hardreg set S, return a string representing it.
1156    Either as 0/1 string, or as hex value depending on the implementation
1157    of hardreg sets.  Note that this string is statically allocated.  */
1158
1159 static char *
1160 hardregset_to_string (s)
1161      HARD_REG_SET s;
1162 {
1163   static char string[/*FIRST_PSEUDO_REGISTER + 30*/1024];
1164 #if FIRST_PSEUDO_REGISTER <= HOST_BITS_PER_WIDE_INT
1165   sprintf (string, HOST_WIDE_INT_PRINT_HEX, s);
1166 #else
1167   char *c = string;
1168   int i,j;
1169   c += sprintf (c, "{ ");
1170   for (i = 0;i < HARD_REG_SET_LONGS; i++)
1171     {
1172       for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
1173           c += sprintf (c, "%s", ( 1 << j) & s[i] ? "1" : "0");
1174       c += sprintf (c, "%s", i ? ", " : "");
1175     }
1176   c += sprintf (c, " }");
1177 #endif
1178   return string;
1179 }
1180
1181 /* For WEB, look at its already colored neighbors, and calculate
1182    the set of hardregs which is not allowed as color for WEB.  Place
1183    that set int *RESULT.  Note that the set of forbidden begin colors
1184    is not the same as all colors taken up by neighbors.  E.g. suppose
1185    two DImode webs, but only the lo-part from one conflicts with the
1186    hipart from the other, and suppose the other gets colors 2 and 3
1187    (it needs two SImode hardregs).  Now the first can take also color
1188    1 or 2, although in those cases there's a partial overlap.  Only
1189    3 can't be used as begin color.  */
1190
1191 static void
1192 calculate_dont_begin (web, result)
1193      struct web *web;
1194      HARD_REG_SET *result;
1195 {
1196   struct conflict_link *wl;
1197   HARD_REG_SET dont_begin;
1198   /* The bits set in dont_begin correspond to the hardregs, at which
1199      WEB may not begin.  This differs from the set of _all_ hardregs which
1200      are taken by WEB's conflicts in the presence of wide webs, where only
1201      some parts conflict with others.  */
1202   CLEAR_HARD_REG_SET (dont_begin);
1203   for (wl = web->conflict_list; wl; wl = wl->next)
1204     {
1205       struct web *w;
1206       struct web *ptarget = alias (wl->t);
1207       struct sub_conflict *sl = wl->sub;
1208       w = sl ? sl->t : wl->t;
1209       while (w)
1210         {
1211           if (ptarget->type == COLORED || ptarget->type == PRECOLORED)
1212             {
1213               struct web *source = (sl) ? sl->s : web;
1214               unsigned int tsize = HARD_REGNO_NREGS (ptarget->color,
1215                                                      GET_MODE (w->orig_x));
1216               /* ssize is only a first guess for the size.  */
1217               unsigned int ssize = HARD_REGNO_NREGS (ptarget->color, GET_MODE
1218                                                      (source->orig_x));
1219               unsigned int tofs = 0;
1220               unsigned int sofs = 0;
1221               /* C1 and C2 can become negative, so unsigned
1222                  would be wrong.  */
1223               int c1, c2;
1224
1225               if (SUBWEB_P (w)
1226                   && GET_MODE_SIZE (GET_MODE (w->orig_x)) >= UNITS_PER_WORD)
1227                 tofs = (SUBREG_BYTE (w->orig_x) / UNITS_PER_WORD);
1228               if (SUBWEB_P (source)
1229                   && GET_MODE_SIZE (GET_MODE (source->orig_x))
1230                      >= UNITS_PER_WORD)
1231                 sofs = (SUBREG_BYTE (source->orig_x) / UNITS_PER_WORD);
1232               c1 = ptarget->color + tofs - sofs - ssize + 1;
1233               c2 = ptarget->color + tofs + tsize - 1 - sofs;
1234               if (c2 >= 0)
1235                 {
1236                   if (c1 < 0)
1237                     c1 = 0;
1238                   /* Because ssize was only guessed above, which influenced our
1239                      begin color (c1), we need adjustment, if for that color
1240                      another size would be needed.  This is done by moving
1241                      c1 to a place, where the last of sources hardregs does not
1242                      overlap the first of targets colors.  */
1243                   while (c1 + sofs
1244                          + HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1
1245                          < ptarget->color + tofs)
1246                     c1++;
1247                   while (c1 > 0 && c1 + sofs
1248                          + HARD_REGNO_NREGS (c1, GET_MODE (source->orig_x)) - 1
1249                          > ptarget->color + tofs)
1250                     c1--;
1251                   for (; c1 <= c2; c1++)
1252                     SET_HARD_REG_BIT (dont_begin, c1);
1253                 }
1254             }
1255           /* The next if() only gets true, if there was no wl->sub at all, in
1256              which case we are only making one go thru this loop with W being
1257              a whole web.  */
1258           if (!sl)
1259             break;
1260           sl = sl->next;
1261           w = sl ? sl->t : NULL;
1262         }
1263     }
1264   COPY_HARD_REG_SET (*result, dont_begin);
1265 }
1266
1267 /* Try to assign a color to WEB.  If HARD if nonzero, we try many
1268    tricks to get it one color, including respilling already colored
1269    neighbors.
1270
1271    We also trie very hard, to not constrain the uncolored non-spill
1272    neighbors, which need more hardregs than we.  Consider a situation, 2
1273    hardregs free for us (0 and 1), and one of our neighbors needs 2
1274    hardregs, and only conflicts with us.  There are 3 hardregs at all.  Now
1275    a simple minded method might choose 1 as color for us.  Then our neighbor
1276    has two free colors (0 and 2) as it should, but they are not consecutive,
1277    so coloring it later would fail.  This leads to nasty problems on
1278    register starved machines, so we try to avoid this.  */
1279
1280 static void
1281 colorize_one_web (web, hard)
1282      struct web *web;
1283      int hard;
1284 {
1285   struct conflict_link *wl;
1286   HARD_REG_SET colors, dont_begin;
1287   int c = -1;
1288   int bestc = -1;
1289   int neighbor_needs= 0;
1290   struct web *fats_parent = NULL;
1291   int num_fat = 0;
1292   int long_blocks = 0;
1293   int best_long_blocks = -1;
1294   HARD_REG_SET fat_colors;
1295   HARD_REG_SET bias;
1296
1297   if (web->regno >= max_normal_pseudo)
1298     hard = 0;
1299
1300   /* First we want to know the colors at which we can't begin.  */
1301   calculate_dont_begin (web, &dont_begin);
1302   CLEAR_HARD_REG_SET (bias);
1303
1304   /* Now setup the set of colors used by our neighbors neighbors,
1305      and search the biggest noncolored neighbor.  */
1306   neighbor_needs = web->add_hardregs + 1;
1307   for (wl = web->conflict_list; wl; wl = wl->next)
1308     {
1309       struct web *w;
1310       struct web *ptarget = alias (wl->t);
1311       struct sub_conflict *sl = wl->sub;
1312       IOR_HARD_REG_SET (bias, ptarget->bias_colors);
1313       w = sl ? sl->t : wl->t;
1314       if (ptarget->type != COLORED && ptarget->type != PRECOLORED
1315           && !ptarget->was_spilled)
1316         while (w)
1317           {
1318             if (find_web_for_subweb (w)->type != COALESCED
1319                 && w->add_hardregs >= neighbor_needs)
1320               {
1321                 neighbor_needs = w->add_hardregs;
1322                 fats_parent = ptarget;
1323                 num_fat++;
1324               }
1325             if (!sl)
1326               break;
1327             sl = sl->next;
1328             w = sl ? sl->t : NULL;
1329           }
1330     }
1331
1332   ra_debug_msg (DUMP_COLORIZE, "colorize web %d [don't begin at %s]", web->id,
1333              hardregset_to_string (dont_begin));
1334
1335   /* If there are some fat neighbors, remember their usable regs,
1336      and how many blocks are free in it for that neighbor.  */
1337   if (num_fat)
1338     {
1339       COPY_HARD_REG_SET (fat_colors, fats_parent->usable_regs);
1340       long_blocks = count_long_blocks (fat_colors, neighbor_needs + 1);
1341     }
1342
1343   /* We break out, if we found a color which doesn't constrain
1344      neighbors, or if we can't find any colors.  */
1345   while (1)
1346     {
1347       HARD_REG_SET call_clobbered;
1348
1349       /* Here we choose a hard-reg for the current web.  For non spill
1350          temporaries we first search in the hardregs for it's preferred
1351          class, then, if we found nothing appropriate, in those of the
1352          alternate class.  For spill temporaries we only search in
1353          usable_regs of this web (which is probably larger than that of
1354          the preferred or alternate class).  All searches first try to
1355          find a non-call-clobbered hard-reg.
1356          XXX this should be more finegraned... First look into preferred
1357          non-callclobbered hardregs, then _if_ the web crosses calls, in
1358          alternate non-cc hardregs, and only _then_ also in preferred cc
1359          hardregs (and alternate ones).  Currently we don't track the number
1360          of calls crossed for webs.  We should.  */
1361       if (web->use_my_regs)
1362         {
1363           COPY_HARD_REG_SET (colors, web->usable_regs);
1364           AND_HARD_REG_SET (colors,
1365                             usable_regs[reg_preferred_class (web->regno)]);
1366         }
1367       else
1368         COPY_HARD_REG_SET (colors,
1369                            usable_regs[reg_preferred_class (web->regno)]);
1370 #ifdef CLASS_CANNOT_CHANGE_MODE
1371       if (web->mode_changed)
1372         AND_COMPL_HARD_REG_SET (colors, reg_class_contents[
1373                                   (int) CLASS_CANNOT_CHANGE_MODE]);
1374 #endif
1375       COPY_HARD_REG_SET (call_clobbered, colors);
1376       AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
1377
1378       /* If this web got a color in the last pass, try to give it the
1379          same color again.  This will to much better colorization
1380          down the line, as we spilled for a certain coloring last time.  */
1381       if (web->old_color)
1382         {
1383           c = web->old_color - 1;
1384           if (!color_usable_p (c, dont_begin, colors,
1385                                PSEUDO_REGNO_MODE (web->regno)))
1386             c = -1;
1387         }
1388       else
1389         c = -1;
1390       if (c < 0)
1391         c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1392                             call_clobbered, PSEUDO_REGNO_MODE (web->regno));
1393       if (c < 0)
1394         c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1395                           colors, PSEUDO_REGNO_MODE (web->regno));
1396
1397       if (c < 0)
1398         {
1399           if (web->use_my_regs)
1400             IOR_HARD_REG_SET (colors, web->usable_regs);
1401           else
1402             IOR_HARD_REG_SET (colors, usable_regs
1403                               [reg_alternate_class (web->regno)]);
1404 #ifdef CLASS_CANNOT_CHANGE_MODE
1405           if (web->mode_changed)
1406             AND_COMPL_HARD_REG_SET (colors, reg_class_contents[
1407                                       (int) CLASS_CANNOT_CHANGE_MODE]);
1408 #endif
1409           COPY_HARD_REG_SET (call_clobbered, colors);
1410           AND_HARD_REG_SET (call_clobbered, call_used_reg_set);
1411
1412           c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1413                             call_clobbered, PSEUDO_REGNO_MODE (web->regno));
1414           if (c < 0)
1415             c = get_biased_reg (dont_begin, bias, web->prefer_colors,
1416                               colors, PSEUDO_REGNO_MODE (web->regno));
1417         }
1418       if (c < 0)
1419         break;
1420       if (bestc < 0)
1421         bestc = c;
1422       /* If one of the yet uncolored neighbors, which is not a potential
1423          spill needs a block of hardregs be sure, not to destroy such a block
1424          by coloring one reg in the middle.  */
1425       if (num_fat)
1426         {
1427           int i;
1428           int new_long;
1429           HARD_REG_SET colors1;
1430           COPY_HARD_REG_SET (colors1, fat_colors);
1431           for (i = 0; i < 1 + web->add_hardregs; i++)
1432             CLEAR_HARD_REG_BIT (colors1, c + i);
1433           new_long = count_long_blocks (colors1, neighbor_needs + 1);
1434           /* If we changed the number of long blocks, and it's now smaller
1435              than needed, we try to avoid this color.  */
1436           if (long_blocks != new_long && new_long < num_fat)
1437             {
1438               if (new_long > best_long_blocks)
1439                 {
1440                   best_long_blocks = new_long;
1441                   bestc = c;
1442                 }
1443               SET_HARD_REG_BIT (dont_begin, c);
1444               ra_debug_msg (DUMP_COLORIZE, " avoid %d", c);
1445             }
1446           else
1447             /* We found a color which doesn't destroy a block.  */
1448             break;
1449         }
1450       /* If we havee no fat neighbors, the current color won't become
1451          "better", so we've found it.  */
1452       else
1453         break;
1454     }
1455   ra_debug_msg (DUMP_COLORIZE, " --> got %d", c < 0 ? bestc : c);
1456   if (bestc >= 0 && c < 0 && !web->was_spilled)
1457     {
1458       /* This is a non-potential-spill web, which got a color, which did
1459          destroy a hardreg block for one of it's neighbors.  We color
1460          this web anyway and hope for the best for the neighbor, if we are
1461          a spill temp.  */
1462       if (1 || web->spill_temp)
1463         c = bestc;
1464       ra_debug_msg (DUMP_COLORIZE, " [constrains neighbors]");
1465     }
1466   ra_debug_msg (DUMP_COLORIZE, "\n");
1467
1468   if (c < 0)
1469     {
1470       /* Guard against a simplified node being spilled.  */
1471       /* Don't abort.  This can happen, when e.g. enough registers
1472          are available in colors, but they are not consecutive.  This is a
1473          very serious issue if this web is a short live one, because
1474          even if we spill this one here, the situation won't become better
1475          in the next iteration.  It probably will have the same conflicts,
1476          those will have the same colors, and we would come here again, for
1477          all parts, in which this one gets splitted by the spill.  This
1478          can result in endless iteration spilling the same register again and
1479          again.  That's why we try to find a neighbor, which spans more
1480          instructions that ourself, and got a color, and try to spill _that_.
1481
1482          if (DLIST_WEB (d)->was_spilled < 0)
1483          abort (); */
1484       if (hard && (!web->was_spilled || web->spill_temp))
1485         {
1486           unsigned int loop;
1487           struct web *try = NULL;
1488           struct web *candidates[8];
1489
1490           ra_debug_msg (DUMP_COLORIZE, "  *** %d spilled, although %s ***\n",
1491                      web->id, web->spill_temp ? "spilltemp" : "non-spill");
1492           /* We make multiple passes over our conflicts, first trying to
1493              spill those webs, which only got a color by chance, but
1494              were potential spill ones, and if that isn't enough, in a second
1495              pass also to spill normal colored webs.  If we still didn't find
1496              a candidate, but we are a spill-temp, we make a third pass
1497              and include also webs, which were targets for coalescing, and
1498              spill those.  */
1499           memset (candidates, 0, sizeof candidates);
1500 #define set_cand(i, w) \
1501           do { \
1502               if (!candidates[(i)] \
1503                   || (candidates[(i)]->spill_cost < (w)->spill_cost)) \
1504                 candidates[(i)] = (w); \
1505           } while (0)
1506           for (wl = web->conflict_list; wl; wl = wl->next)
1507             {
1508               struct web *w = wl->t;
1509               struct web *aw = alias (w);
1510               /* If we are a spill-temp, we also look at webs coalesced
1511                  to precolored ones.  Otherwise we only look at webs which
1512                  themself were colored, or coalesced to one.  */
1513               if (aw->type == PRECOLORED && w != aw && web->spill_temp
1514                   && flag_ra_optimistic_coalescing)
1515                 {
1516                   if (!w->spill_temp)
1517                     set_cand (4, w);
1518                   else if (web->spill_temp == 2
1519                            && w->spill_temp == 2
1520                            && w->spill_cost < web->spill_cost)
1521                     set_cand (5, w);
1522                   else if (web->spill_temp != 2
1523                            && (w->spill_temp == 2
1524                                || w->spill_cost < web->spill_cost))
1525                     set_cand (6, w);
1526                   continue;
1527                 }
1528               if (aw->type != COLORED)
1529                 continue;
1530               if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
1531                   && w->was_spilled)
1532                 {
1533                   if (w->spill_cost < web->spill_cost)
1534                     set_cand (0, w);
1535                   else if (web->spill_temp)
1536                     set_cand (1, w);
1537                 }
1538               if (w->type == COLORED && !w->spill_temp && !w->is_coalesced
1539                   && !w->was_spilled)
1540                 {
1541                   if (w->spill_cost < web->spill_cost)
1542                     set_cand (2, w);
1543                   else if (web->spill_temp && web->spill_temp != 2)
1544                     set_cand (3, w);
1545                 }
1546               if (web->spill_temp)
1547                 {
1548                   if (w->type == COLORED && w->spill_temp == 2
1549                       && !w->is_coalesced
1550                       && (w->spill_cost < web->spill_cost
1551                           || web->spill_temp != 2))
1552                     set_cand (4, w);
1553                   if (!aw->spill_temp)
1554                     set_cand (5, aw);
1555                   if (aw->spill_temp == 2
1556                       && (aw->spill_cost < web->spill_cost
1557                           || web->spill_temp != 2))
1558                     set_cand (6, aw);
1559                   /* For boehm-gc/misc.c.  If we are a difficult spilltemp,
1560                      also coalesced neighbors are a chance, _even_ if they
1561                      too are spilltemps.  At least their coalescing can be
1562                      broken up, which may be reset usable_regs, and makes
1563                      it easier colorable.  */
1564                   if (web->spill_temp != 2 && aw->is_coalesced
1565                       && flag_ra_optimistic_coalescing)
1566                     set_cand (7, aw);
1567                 }
1568             }
1569           for (loop = 0; try == NULL && loop < 8; loop++)
1570             if (candidates[loop])
1571               try = candidates[loop];
1572 #undef set_cand
1573           if (try)
1574             {
1575               int old_c = try->color;
1576               if (try->type == COALESCED)
1577                 {
1578                   if (alias (try)->type != PRECOLORED)
1579                     abort ();
1580                   ra_debug_msg (DUMP_COLORIZE, "  breaking alias %d -> %d\n",
1581                              try->id, alias (try)->id);
1582                   break_precolored_alias (try);
1583                   colorize_one_web (web, hard);
1584                 }
1585               else
1586                 {
1587                   remove_list (try->dlink, &WEBS(COLORED));
1588                   put_web (try, SPILLED);
1589                   /* Now try to colorize us again.  Can recursively make other
1590                      webs also spill, until there are no more unspilled
1591                      neighbors.  */
1592                   ra_debug_msg (DUMP_COLORIZE, "  trying to spill %d\n", try->id);
1593                   colorize_one_web (web, hard);
1594                   if (web->type != COLORED)
1595                     {
1596                       /* We tried recursively to spill all already colored
1597                          neighbors, but we are still uncolorable.  So it made
1598                          no sense to spill those neighbors.  Recolor them.  */
1599                       remove_list (try->dlink, &WEBS(SPILLED));
1600                       put_web (try, COLORED);
1601                       try->color = old_c;
1602                       ra_debug_msg (DUMP_COLORIZE,
1603                                     "  spilling %d was useless\n", try->id);
1604                     }
1605                   else
1606                     {
1607                       ra_debug_msg (DUMP_COLORIZE,
1608                                     "  to spill %d was a good idea\n",
1609                                     try->id);
1610                       remove_list (try->dlink, &WEBS(SPILLED));
1611                       if (try->was_spilled)
1612                         colorize_one_web (try, 0);
1613                       else
1614                         colorize_one_web (try, hard - 1);
1615                     }
1616                 }
1617             }
1618           else
1619             /* No more chances to get a color, so give up hope and
1620                spill us.  */
1621             put_web (web, SPILLED);
1622         }
1623       else
1624         put_web (web, SPILLED);
1625     }
1626   else
1627     {
1628       put_web (web, COLORED);
1629       web->color = c;
1630       if (flag_ra_biased)
1631         {
1632           int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
1633           for (wl = web->conflict_list; wl; wl = wl->next)
1634             {
1635               struct web *ptarget = alias (wl->t);
1636               int i;
1637               for (i = 0; i < nregs; i++)
1638                 SET_HARD_REG_BIT (ptarget->bias_colors, c + i);
1639             }
1640         }
1641     }
1642   if (web->regno >= max_normal_pseudo && web->type == SPILLED)
1643     {
1644       web->color = an_unusable_color;
1645       remove_list (web->dlink, &WEBS(SPILLED));
1646       put_web (web, COLORED);
1647     }
1648   if (web->type == SPILLED && flag_ra_optimistic_coalescing
1649       && web->is_coalesced)
1650     {
1651       ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
1652       restore_conflicts_from_coalesce (web);
1653       break_aliases_to_web (web);
1654       insert_coalesced_conflicts ();
1655       ra_debug_msg (DUMP_COLORIZE, "\n");
1656       remove_list (web->dlink, &WEBS(SPILLED));
1657       put_web (web, SELECT);
1658       web->color = -1;
1659     }
1660 }
1661
1662 /* Assign the colors to all nodes on the select stack.  And update the
1663    colors of coalesced webs.  */
1664
1665 static void
1666 assign_colors ()
1667 {
1668   struct dlist *d;
1669
1670   while (WEBS(SELECT))
1671     {
1672       d = pop_list (&WEBS(SELECT));
1673       colorize_one_web (DLIST_WEB (d), 1);
1674     }
1675
1676   for (d = WEBS(COALESCED); d; d = d->next)
1677     {
1678       struct web *a = alias (DLIST_WEB (d));
1679       DLIST_WEB (d)->color = a->color;
1680     }
1681 }
1682
1683 /* WEB is a spilled web.  Look if we can improve the cost of the graph,
1684    by coloring WEB, even if we then need to spill some of it's neighbors.
1685    For this we calculate the cost for each color C, that results when we
1686    _would_ give WEB color C (i.e. the cost of the then spilled neighbors).
1687    If the lowest cost among them is smaller than the spillcost of WEB, we
1688    do that recoloring, and instead spill the neighbors.
1689
1690    This can sometime help, when due to irregularities in register file,
1691    and due to multi word pseudos, the colorization is suboptimal.  But
1692    be aware, that currently this pass is quite slow.  */
1693
1694 static void
1695 try_recolor_web (web)
1696      struct web *web;
1697 {
1698   struct conflict_link *wl;
1699   unsigned HOST_WIDE_INT *cost_neighbors;
1700   unsigned int *min_color;
1701   int newcol, c;
1702   HARD_REG_SET precolored_neighbors, spill_temps;
1703   HARD_REG_SET possible_begin, wide_seen;
1704   cost_neighbors = (unsigned HOST_WIDE_INT *)
1705     xcalloc (FIRST_PSEUDO_REGISTER, sizeof (cost_neighbors[0]));
1706   /* For each hard-regs count the number of preceding hardregs, which
1707      would overlap this color, if used in WEB's mode.  */
1708   min_color = (unsigned int *) xcalloc (FIRST_PSEUDO_REGISTER, sizeof (int));
1709   CLEAR_HARD_REG_SET (possible_begin);
1710   for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1711     {
1712       int i, nregs;
1713       if (!HARD_REGNO_MODE_OK (c, GET_MODE (web->orig_x)))
1714         continue;
1715       nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
1716       for (i = 0; i < nregs; i++)
1717         if (!TEST_HARD_REG_BIT (web->usable_regs, c + i))
1718           break;
1719       if (i < nregs || nregs == 0)
1720         continue;
1721       SET_HARD_REG_BIT (possible_begin, c);
1722       for (; nregs--;)
1723         if (!min_color[c + nregs])
1724           min_color[c + nregs] = 1 + c;
1725     }
1726   CLEAR_HARD_REG_SET (precolored_neighbors);
1727   CLEAR_HARD_REG_SET (spill_temps);
1728   CLEAR_HARD_REG_SET (wide_seen);
1729   for (wl = web->conflict_list; wl; wl = wl->next)
1730     {
1731       HARD_REG_SET dont_begin;
1732       struct web *web2 = alias (wl->t);
1733       struct conflict_link *nn;
1734       int c1, c2;
1735       int wide_p = 0;
1736       if (wl->t->type == COALESCED || web2->type != COLORED)
1737         {
1738           if (web2->type == PRECOLORED)
1739             {
1740               c1 = min_color[web2->color];
1741               c1 = (c1 == 0) ? web2->color : (c1 - 1);
1742               c2 = web2->color;
1743               for (; c1 <= c2; c1++)
1744                 SET_HARD_REG_BIT (precolored_neighbors, c1);
1745             }
1746           continue;
1747         }
1748       /* Mark colors for which some wide webs are involved.  For
1749          those the independent sets are not simply one-node graphs, so
1750          they can't be recolored independ from their neighborhood.  This
1751          means, that our cost calculation can be incorrect (assuming it
1752          can avoid spilling a web because it thinks some colors are available,
1753          although it's neighbors which itself need recoloring might take
1754          away exactly those colors).  */
1755       if (web2->add_hardregs)
1756         wide_p = 1;
1757       for (nn = web2->conflict_list; nn && !wide_p; nn = nn->next)
1758         if (alias (nn->t)->add_hardregs)
1759           wide_p = 1;
1760       calculate_dont_begin (web2, &dont_begin);
1761       c1 = min_color[web2->color];
1762       /* Note that min_color[] contains 1-based values (zero means
1763          undef).  */
1764       c1 = c1 == 0 ? web2->color : (c1 - 1);
1765       c2 = web2->color + HARD_REGNO_NREGS (web2->color, GET_MODE
1766                                            (web2->orig_x)) - 1;
1767       for (; c1 <= c2; c1++)
1768         if (TEST_HARD_REG_BIT (possible_begin, c1))
1769           {
1770             int nregs;
1771             HARD_REG_SET colors;
1772             nregs = HARD_REGNO_NREGS (c1, GET_MODE (web->orig_x));
1773             COPY_HARD_REG_SET (colors, web2->usable_regs);
1774             for (; nregs--;)
1775               CLEAR_HARD_REG_BIT (colors, c1 + nregs);
1776             if (wide_p)
1777               SET_HARD_REG_BIT (wide_seen, c1);
1778             if (get_free_reg (dont_begin, colors,
1779                               GET_MODE (web2->orig_x)) < 0)
1780               {
1781                 if (web2->spill_temp)
1782                   SET_HARD_REG_BIT (spill_temps, c1);
1783                 else
1784                   cost_neighbors[c1] += web2->spill_cost;
1785               }
1786           }
1787     }
1788   newcol = -1;
1789   for (c = 0; c < FIRST_PSEUDO_REGISTER; c++)
1790     if (TEST_HARD_REG_BIT (possible_begin, c)
1791         && !TEST_HARD_REG_BIT (precolored_neighbors, c)
1792         && !TEST_HARD_REG_BIT (spill_temps, c)
1793         && (newcol == -1
1794             || cost_neighbors[c] < cost_neighbors[newcol]))
1795       newcol = c;
1796   if (newcol >= 0 && cost_neighbors[newcol] < web->spill_cost)
1797     {
1798       int nregs = HARD_REGNO_NREGS (newcol, GET_MODE (web->orig_x));
1799       unsigned HOST_WIDE_INT cost = 0;
1800       int *old_colors;
1801       struct conflict_link *wl_next;
1802       ra_debug_msg (DUMP_COLORIZE, "try to set web %d to color %d\n", web->id,
1803                  newcol);
1804       remove_list (web->dlink, &WEBS(SPILLED));
1805       put_web (web, COLORED);
1806       web->color = newcol;
1807       old_colors = (int *) xcalloc (num_webs, sizeof (int));
1808       for (wl = web->conflict_list; wl; wl = wl_next)
1809         {
1810           struct web *web2 = alias (wl->t);
1811           /* If web2 is a coalesce-target, and will become spilled
1812              below in colorize_one_web(), and the current conflict wl
1813              between web and web2 was only the result of that coalescing
1814              this conflict will be deleted, making wl invalid.  So save
1815              the next conflict right now.  Note that if web2 has indeed
1816              such state, then wl->next can not be deleted in this
1817              iteration.  */
1818           wl_next = wl->next;
1819           if (web2->type == COLORED)
1820             {
1821               int nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE
1822                                              (web2->orig_x));
1823               if (web->color >= web2->color + nregs2
1824                   || web2->color >= web->color + nregs)
1825                 continue;
1826               old_colors[web2->id] = web2->color + 1;
1827               web2->color = -1;
1828               remove_list (web2->dlink, &WEBS(COLORED));
1829               web2->type = SELECT;
1830               /* Allow webs to be spilled.  */
1831               if (web2->spill_temp == 0 || web2->spill_temp == 2)
1832                 web2->was_spilled = 1;
1833               colorize_one_web (web2, 1);
1834               if (web2->type == SPILLED)
1835                 cost += web2->spill_cost;
1836             }
1837         }
1838       /* The actual cost may be smaller than the guessed one, because
1839          partial conflicts could result in some conflicting webs getting
1840          a color, where we assumed it must be spilled.  See the comment
1841          above what happens, when wide webs are involved, and why in that
1842          case there might actually be some webs spilled although thought to
1843          be colorable.  */
1844       if (cost > cost_neighbors[newcol]
1845           && nregs == 1 && !TEST_HARD_REG_BIT (wide_seen, newcol))
1846         abort ();
1847       /* But if the new spill-cost is higher than our own, then really loose.
1848          Respill us and recolor neighbors as before.  */
1849       if (cost > web->spill_cost)
1850         {
1851           ra_debug_msg (DUMP_COLORIZE,
1852                      "reset coloring of web %d, too expensive\n", web->id);
1853           remove_list (web->dlink, &WEBS(COLORED));
1854           web->color = -1;
1855           put_web (web, SPILLED);
1856           for (wl = web->conflict_list; wl; wl = wl->next)
1857             {
1858               struct web *web2 = alias (wl->t);
1859               if (old_colors[web2->id])
1860                 {
1861                   if (web2->type == SPILLED)
1862                     {
1863                       remove_list (web2->dlink, &WEBS(SPILLED));
1864                       web2->color = old_colors[web2->id] - 1;
1865                       put_web (web2, COLORED);
1866                     }
1867                   else if (web2->type == COLORED)
1868                     web2->color = old_colors[web2->id] - 1;
1869                   else if (web2->type == SELECT)
1870                     /* This means, that WEB2 once was a part of a coalesced
1871                        web, which got spilled in the above colorize_one_web()
1872                        call, and whose parts then got splitted and put back
1873                        onto the SELECT stack.  As the cause for that splitting
1874                        (the coloring of WEB) was worthless, we should again
1875                        coalesce the parts, as they were before.  For now we
1876                        simply leave them SELECTed, for our caller to take
1877                        care.  */
1878                     ;
1879                   else
1880                     abort ();
1881                 }
1882             }
1883         }
1884       free (old_colors);
1885     }
1886   free (min_color);
1887   free (cost_neighbors);
1888 }
1889
1890 /* This ensures that all conflicts of coalesced webs are seen from
1891    the webs coalesced into.  combine() only adds the conflicts which
1892    at the time of combining were not already SELECTed or COALESCED
1893    to not destroy num_conflicts.  Here we add all remaining conflicts
1894    and thereby destroy num_conflicts.  This should be used when num_conflicts
1895    isn't used anymore, e.g. on a completely colored graph.  */
1896
1897 static void
1898 insert_coalesced_conflicts ()
1899 {
1900   struct dlist *d;
1901   for (d = WEBS(COALESCED); 0 && d; d = d->next)
1902     {
1903       struct web *web = DLIST_WEB (d);
1904       struct web *aweb = alias (web);
1905       struct conflict_link *wl;
1906       for (wl = web->conflict_list; wl; wl = wl->next)
1907         {
1908           struct web *tweb = aweb;
1909           int i;
1910           int nregs = 1 + web->add_hardregs;
1911           if (aweb->type == PRECOLORED)
1912             nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x));
1913           for (i = 0; i < nregs; i++)
1914             {
1915               if (aweb->type == PRECOLORED)
1916                 tweb = hardreg2web[i + aweb->color];
1917               /* There might be some conflict edges laying around
1918                  where the usable_regs don't intersect.  This can happen
1919                  when first some webs were coalesced and conflicts
1920                  propagated, then some combining narrowed usable_regs and
1921                  further coalescing ignored those conflicts.  Now there are
1922                  some edges to COALESCED webs but not to it's alias.
1923                  So abort only when they really should conflict.  */
1924               if ((!(tweb->type == PRECOLORED
1925                      || TEST_BIT (sup_igraph, tweb->id * num_webs + wl->t->id))
1926                    || !(wl->t->type == PRECOLORED
1927                         || TEST_BIT (sup_igraph,
1928                                      wl->t->id * num_webs + tweb->id)))
1929                   && hard_regs_intersect_p (&tweb->usable_regs,
1930                                             &wl->t->usable_regs))
1931                 abort ();
1932               /*if (wl->sub == NULL)
1933                 record_conflict (tweb, wl->t);
1934               else
1935                 {
1936                   struct sub_conflict *sl;
1937                   for (sl = wl->sub; sl; sl = sl->next)
1938                     record_conflict (tweb, sl->t);
1939                 }*/
1940               if (aweb->type != PRECOLORED)
1941                 break;
1942             }
1943         }
1944     }
1945 }
1946
1947 /* A function suitable to pass to qsort().  Compare the spill costs
1948    of webs W1 and W2.  When used by qsort, this would order webs with
1949    largest cost first.  */
1950
1951 static int
1952 comp_webs_maxcost (w1, w2)
1953      const void *w1, *w2;
1954 {
1955   struct web *web1 = *(struct web **)w1;
1956   struct web *web2 = *(struct web **)w2;
1957   if (web1->spill_cost > web2->spill_cost)
1958     return -1;
1959   else if (web1->spill_cost < web2->spill_cost)
1960     return 1;
1961   else
1962     return 0;
1963 }
1964
1965 /* This tries to recolor all spilled webs.  See try_recolor_web()
1966    how this is done.  This just calls it for each spilled web.  */
1967
1968 static void
1969 recolor_spills ()
1970 {
1971   unsigned int i, num;
1972   struct web **order2web;
1973   num = num_webs - num_subwebs;
1974   order2web = (struct web **) xmalloc (num * sizeof (order2web[0]));
1975   for (i = 0; i < num; i++)
1976     {
1977       order2web[i] = id2web[i];
1978       /* If we aren't breaking aliases, combine() wasn't merging the
1979          spill_costs.  So do that here to have sane measures.  */
1980       if (!flag_ra_merge_spill_costs && id2web[i]->type == COALESCED)
1981         alias (id2web[i])->spill_cost += id2web[i]->spill_cost;
1982     }
1983   qsort (order2web, num, sizeof (order2web[0]), comp_webs_maxcost);
1984   insert_coalesced_conflicts ();
1985   dump_graph_cost (DUMP_COSTS, "before spill-recolor");
1986   for (i = 0; i < num; i++)
1987     {
1988       struct web *web = order2web[i];
1989       if (web->type == SPILLED)
1990         try_recolor_web (web);
1991     }
1992   /* It might have been decided in try_recolor_web() (in colorize_one_web())
1993      that a coalesced web should be spilled, so it was put on the
1994      select stack.  Those webs need recoloring again, and all remaining
1995      coalesced webs might need their color updated, so simply call
1996      assign_colors() again.  */
1997   assign_colors ();
1998   free (order2web);
1999 }
2000
2001 /* This checks the current color assignment for obvious errors,
2002    like two conflicting webs overlapping in colors, or the used colors
2003    not being in usable regs.  */
2004
2005 static void
2006 check_colors ()
2007 {
2008   unsigned int i;
2009   for (i = 0; i < num_webs - num_subwebs; i++)
2010     {
2011       struct web *web = id2web[i];
2012       struct web *aweb = alias (web);
2013       struct conflict_link *wl;
2014       int nregs, c;
2015       if (aweb->type == SPILLED || web->regno >= max_normal_pseudo)
2016         continue;
2017       else if (aweb->type == COLORED)
2018         nregs = HARD_REGNO_NREGS (aweb->color, GET_MODE (web->orig_x));
2019       else if (aweb->type == PRECOLORED)
2020         nregs = 1;
2021       else
2022         abort ();
2023       /* The color must be valid for the original usable_regs.  */
2024       for (c = 0; c < nregs; c++)
2025         if (!TEST_HARD_REG_BIT (web->usable_regs, aweb->color + c))
2026           abort ();
2027       /* Search the original (pre-coalesce) conflict list.  In the current
2028          one some imprecise conflicts may be noted (due to combine() or
2029          insert_coalesced_conflicts() relocating partial conflicts) making
2030          it look like some wide webs are in conflict and having the same
2031          color.  */
2032       wl = (web->have_orig_conflicts ? web->orig_conflict_list
2033             : web->conflict_list);
2034       for (; wl; wl = wl->next)
2035         if (wl->t->regno >= max_normal_pseudo)
2036           continue;
2037         else if (!wl->sub)
2038           {
2039             struct web *web2 = alias (wl->t);
2040             int nregs2;
2041             if (web2->type == COLORED)
2042               nregs2 = HARD_REGNO_NREGS (web2->color, GET_MODE (web2->orig_x));
2043             else if (web2->type == PRECOLORED)
2044               nregs2 = 1;
2045             else
2046               continue;
2047             if (aweb->color >= web2->color + nregs2
2048                 || web2->color >= aweb->color + nregs)
2049               continue;
2050             abort ();
2051           }
2052         else
2053           {
2054             struct sub_conflict *sl;
2055             int scol = aweb->color;
2056             int tcol = alias (wl->t)->color;
2057             if (alias (wl->t)->type == SPILLED)
2058               continue;
2059             for (sl = wl->sub; sl; sl = sl->next)
2060               {
2061                 int ssize = HARD_REGNO_NREGS (scol, GET_MODE (sl->s->orig_x));
2062                 int tsize = HARD_REGNO_NREGS (tcol, GET_MODE (sl->t->orig_x));
2063                 int sofs = 0, tofs = 0;
2064                 if (SUBWEB_P (sl->t)
2065                     && GET_MODE_SIZE (GET_MODE (sl->t->orig_x)) >= UNITS_PER_WORD)
2066                   tofs = (SUBREG_BYTE (sl->t->orig_x) / UNITS_PER_WORD);
2067                 if (SUBWEB_P (sl->s)
2068                     && GET_MODE_SIZE (GET_MODE (sl->s->orig_x))
2069                        >= UNITS_PER_WORD)
2070                   sofs = (SUBREG_BYTE (sl->s->orig_x) / UNITS_PER_WORD);
2071                 if ((tcol + tofs >= scol + sofs + ssize)
2072                     || (scol + sofs >= tcol + tofs + tsize))
2073                   continue;
2074                 abort ();
2075               }
2076           }
2077     }
2078 }
2079
2080 /* WEB was a coalesced web.  Make it unaliased again, and put it
2081    back onto SELECT stack.  */
2082
2083 static void
2084 unalias_web (web)
2085      struct web *web;
2086 {
2087   web->alias = NULL;
2088   web->is_coalesced = 0;
2089   web->color = -1;
2090   /* Well, initially everything was spilled, so it isn't incorrect,
2091      that also the individual parts can be spilled.
2092      XXX this isn't entirely correct, as we also relaxed the
2093      spill_temp flag in combine(), which might have made components
2094      spill, although they were a short or spilltemp web.  */
2095   web->was_spilled = 1;
2096   remove_list (web->dlink, &WEBS(COALESCED));
2097   /* Spilltemps must be colored right now (i.e. as early as possible),
2098      other webs can be deferred to the end (the code building the
2099      stack assumed that in this stage only one web was colored).  */
2100   if (web->spill_temp && web->spill_temp != 2)
2101     put_web (web, SELECT);
2102   else
2103     put_web_at_end (web, SELECT);
2104 }
2105
2106 /* WEB is a _target_ for coalescing which got spilled.
2107    Break all aliases to WEB, and restore some of its member to the state
2108    they were before coalescing.  Due to the suboptimal structure of
2109    the interference graph we need to go through all coalesced webs.
2110    Somewhen we'll change this to be more sane.  */
2111
2112 static void
2113 break_aliases_to_web (web)
2114      struct web *web;
2115 {
2116   struct dlist *d, *d_next;
2117   if (web->type != SPILLED)
2118     abort ();
2119   for (d = WEBS(COALESCED); d; d = d_next)
2120     {
2121       struct web *other = DLIST_WEB (d);
2122       d_next = d->next;
2123       /* Beware: Don't use alias() here.  We really want to check only
2124          one level of aliasing, i.e. only break up webs directly
2125          aliased to WEB, not also those aliased through other webs.  */
2126       if (other->alias == web)
2127         {
2128           unalias_web (other);
2129           ra_debug_msg (DUMP_COLORIZE, " %d", other->id);
2130         }
2131     }
2132   web->spill_temp = web->orig_spill_temp;
2133   web->spill_cost = web->orig_spill_cost;
2134   /* Beware: The following possibly widens usable_regs again.  While
2135      it was narrower there might have been some conflicts added which got
2136      ignored because of non-intersecting hardregsets.  All those conflicts
2137      would now matter again.  Fortunately we only add conflicts when
2138      coalescing, which is also the time of narrowing.  And we remove all
2139      those added conflicts again now that we unalias this web.
2140      Therefore this is safe to do.  */
2141   COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
2142   web->is_coalesced = 0;
2143   web->num_aliased = 0;
2144   web->was_spilled = 1;
2145   /* Reset is_coalesced flag for webs which itself are target of coalescing.
2146      It was cleared above if it was coalesced to WEB.  */
2147   for (d = WEBS(COALESCED); d; d = d->next)
2148     DLIST_WEB (d)->alias->is_coalesced = 1;
2149 }
2150
2151 /* WEB is a web coalesced into a precolored one.  Break that alias,
2152    making WEB SELECTed again.  Also restores the conflicts which resulted
2153    from initially coalescing both.  */
2154
2155 static void
2156 break_precolored_alias (web)
2157      struct web *web;
2158 {
2159   struct web *pre = web->alias;
2160   struct conflict_link *wl;
2161   unsigned int c = pre->color;
2162   unsigned int nregs = HARD_REGNO_NREGS (c, GET_MODE (web->orig_x));
2163   if (pre->type != PRECOLORED)
2164     abort ();
2165   unalias_web (web);
2166   /* Now we need to look at each conflict X of WEB, if it conflicts
2167      with [PRE, PRE+nregs), and remove such conflicts, of X has not other
2168      conflicts, which are coalesced into those precolored webs.  */
2169   for (wl = web->conflict_list; wl; wl = wl->next)
2170     {
2171       struct web *x = wl->t;
2172       struct web *y;
2173       unsigned int i;
2174       struct conflict_link *wl2;
2175       struct conflict_link **pcl;
2176       HARD_REG_SET regs;
2177       if (!x->have_orig_conflicts)
2178         continue;
2179       /* First look at which colors can not go away, due to other coalesces
2180          still existing.  */
2181       CLEAR_HARD_REG_SET (regs);
2182       for (i = 0; i < nregs; i++)
2183         SET_HARD_REG_BIT (regs, c + i);
2184       for (wl2 = x->conflict_list; wl2; wl2 = wl2->next)
2185         if (wl2->t->type == COALESCED && alias (wl2->t)->type == PRECOLORED)
2186           CLEAR_HARD_REG_BIT (regs, alias (wl2->t)->color);
2187       /* Now also remove the colors of those conflicts which already
2188          were there before coalescing at all.  */
2189       for (wl2 = x->orig_conflict_list; wl2; wl2 = wl2->next)
2190         if (wl2->t->type == PRECOLORED)
2191           CLEAR_HARD_REG_BIT (regs, wl2->t->color);
2192       /* The colors now still set are those for which WEB was the last
2193          cause, i.e. those which can be removed.  */
2194       y = NULL;
2195       for (i = 0; i < nregs; i++)
2196         if (TEST_HARD_REG_BIT (regs, c + i))
2197           {
2198             struct web *sub;
2199             y = hardreg2web[c + i];
2200             RESET_BIT (sup_igraph, x->id * num_webs + y->id);
2201             RESET_BIT (sup_igraph, y->id * num_webs + x->id);
2202             RESET_BIT (igraph, igraph_index (x->id, y->id));
2203             for (sub = x->subreg_next; sub; sub = sub->subreg_next)
2204               RESET_BIT (igraph, igraph_index (sub->id, y->id));
2205           }
2206       if (!y)
2207         continue;
2208       pcl = &(x->conflict_list);
2209       while (*pcl)
2210         {
2211           struct web *y = (*pcl)->t;
2212           if (y->type != PRECOLORED || !TEST_HARD_REG_BIT (regs, y->color))
2213             pcl = &((*pcl)->next);
2214           else
2215             *pcl = (*pcl)->next;
2216         }
2217     }
2218 }
2219
2220 /* WEB is a spilled web which was target for coalescing.
2221    Delete all interference edges which were added due to that coalescing,
2222    and break up the coalescing.  */
2223
2224 static void
2225 restore_conflicts_from_coalesce (web)
2226      struct web *web;
2227 {
2228   struct conflict_link **pcl;
2229   struct conflict_link *wl;
2230   pcl = &(web->conflict_list);
2231   /* No original conflict list means no conflict was added at all
2232      after building the graph.  So neither we nor any neighbors have
2233      conflicts due to this coalescing.  */
2234   if (!web->have_orig_conflicts)
2235     return;
2236   while (*pcl)
2237     {
2238       struct web *other = (*pcl)->t;
2239       for (wl = web->orig_conflict_list; wl; wl = wl->next)
2240         if (wl->t == other)
2241           break;
2242       if (wl)
2243         {
2244           /* We found this conflict also in the original list, so this
2245              was no new conflict.  */
2246           pcl = &((*pcl)->next);
2247         }
2248       else
2249         {
2250           /* This is a new conflict, so delete it from us and
2251              the neighbor.  */
2252           struct conflict_link **opcl;
2253           struct conflict_link *owl;
2254           struct sub_conflict *sl;
2255           wl = *pcl;
2256           *pcl = wl->next;
2257           if (!other->have_orig_conflicts && other->type != PRECOLORED)
2258             abort ();
2259           for (owl = other->orig_conflict_list; owl; owl = owl->next)
2260             if (owl->t == web)
2261               break;
2262           if (owl)
2263             abort ();
2264           opcl = &(other->conflict_list);
2265           while (*opcl)
2266             {
2267               if ((*opcl)->t == web)
2268                 {
2269                   owl = *opcl;
2270                   *opcl = owl->next;
2271                   break;
2272                 }
2273               else
2274                 {
2275                   opcl = &((*opcl)->next);
2276                 }
2277             }
2278           if (!owl && other->type != PRECOLORED)
2279             abort ();
2280           /* wl and owl contain the edge data to be deleted.  */
2281           RESET_BIT (sup_igraph, web->id * num_webs + other->id);
2282           RESET_BIT (sup_igraph, other->id * num_webs + web->id);
2283           RESET_BIT (igraph, igraph_index (web->id, other->id));
2284           for (sl = wl->sub; sl; sl = sl->next)
2285             RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
2286           if (other->type != PRECOLORED)
2287             {
2288               for (sl = owl->sub; sl; sl = sl->next)
2289                 RESET_BIT (igraph, igraph_index (sl->s->id, sl->t->id));
2290             }
2291         }
2292     }
2293
2294   /* We must restore usable_regs because record_conflict will use it.  */
2295   COPY_HARD_REG_SET (web->usable_regs, web->orig_usable_regs);
2296   /* We might have deleted some conflicts above, which really are still
2297      there (diamond pattern coalescing).  This is because we don't reference
2298      count interference edges but some of them were the result of different
2299      coalesces.  */
2300   for (wl = web->conflict_list; wl; wl = wl->next)
2301     if (wl->t->type == COALESCED)
2302       {
2303         struct web *tweb;
2304         for (tweb = wl->t->alias; tweb; tweb = tweb->alias)
2305           {
2306             if (wl->sub == NULL)
2307               record_conflict (web, tweb);
2308             else
2309               {
2310                 struct sub_conflict *sl;
2311                 for (sl = wl->sub; sl; sl = sl->next)
2312                   {
2313                     struct web *sweb = NULL;
2314                     if (SUBWEB_P (sl->t))
2315                       sweb = find_subweb (tweb, sl->t->orig_x);
2316                     if (!sweb)
2317                       sweb = tweb;
2318                     record_conflict (sl->s, sweb);
2319                   }
2320               }
2321             if (tweb->type != COALESCED)
2322               break;
2323           }
2324       }
2325 }
2326
2327 /* Repeatedly break aliases for spilled webs, which were target for
2328    coalescing, and recolorize the resulting parts.  Do this as long as
2329    there are any spilled coalesce targets.  */
2330
2331 static void
2332 break_coalesced_spills ()
2333 {
2334   int changed = 0;
2335   while (1)
2336     {
2337       struct dlist *d;
2338       struct web *web;
2339       for (d = WEBS(SPILLED); d; d = d->next)
2340         if (DLIST_WEB (d)->is_coalesced)
2341           break;
2342       if (!d)
2343         break;
2344       changed = 1;
2345       web = DLIST_WEB (d);
2346       ra_debug_msg (DUMP_COLORIZE, "breaking aliases to web %d:", web->id);
2347       restore_conflicts_from_coalesce (web);
2348       break_aliases_to_web (web);
2349       /* WEB was a spilled web and isn't anymore.  Everything coalesced
2350          to WEB is now SELECTed and might potentially get a color.
2351          If those other webs were itself targets of coalescing it might be
2352          that there are still some conflicts from aliased webs missing,
2353          because they were added in combine() right into the now
2354          SELECTed web.  So we need to add those missing conflicts here.  */
2355       insert_coalesced_conflicts ();
2356       ra_debug_msg (DUMP_COLORIZE, "\n");
2357       remove_list (d, &WEBS(SPILLED));
2358       put_web (web, SELECT);
2359       web->color = -1;
2360       while (WEBS(SELECT))
2361         {
2362           d = pop_list (&WEBS(SELECT));
2363           colorize_one_web (DLIST_WEB (d), 1);
2364         }
2365     }
2366   if (changed)
2367     {
2368       struct dlist *d;
2369       for (d = WEBS(COALESCED); d; d = d->next)
2370         {
2371           struct web *a = alias (DLIST_WEB (d));
2372           DLIST_WEB (d)->color = a->color;
2373         }
2374     }
2375   dump_graph_cost (DUMP_COSTS, "after alias-breaking");
2376 }
2377
2378 /* A structure for fast hashing of a pair of webs.
2379    Used to cumulate savings (from removing copy insns) for coalesced webs.
2380    All the pairs are also put into a single linked list.  */
2381 struct web_pair
2382 {
2383   struct web_pair *next_hash;
2384   struct web_pair *next_list;
2385   struct web *smaller;
2386   struct web *larger;
2387   unsigned int conflicts;
2388   unsigned HOST_WIDE_INT cost;
2389 };
2390
2391 /* The actual hash table.  */
2392 #define WEB_PAIR_HASH_SIZE 8192
2393 static struct web_pair *web_pair_hash[WEB_PAIR_HASH_SIZE];
2394 static struct web_pair *web_pair_list;
2395 static unsigned int num_web_pairs;
2396
2397 /* Clear the hash table of web pairs.  */
2398
2399 static void
2400 init_web_pairs ()
2401 {
2402   memset (web_pair_hash, 0, sizeof web_pair_hash);
2403   num_web_pairs = 0;
2404   web_pair_list = NULL;
2405 }
2406
2407 /* Given two webs connected by a move with cost COST which together
2408    have CONFLICTS conflicts, add that pair to the hash table, or if
2409    already in, cumulate the costs and conflict number.  */
2410
2411 static void
2412 add_web_pair_cost (web1, web2, cost, conflicts)
2413      struct web *web1, *web2;
2414      unsigned HOST_WIDE_INT cost;
2415      unsigned int conflicts;
2416 {
2417   unsigned int hash;
2418   struct web_pair *p;
2419   if (web1->id > web2->id)
2420     {
2421       struct web *h = web1;
2422       web1 = web2;
2423       web2 = h;
2424     }
2425   hash = (web1->id * num_webs + web2->id) % WEB_PAIR_HASH_SIZE;
2426   for (p = web_pair_hash[hash]; p; p = p->next_hash)
2427     if (p->smaller == web1 && p->larger == web2)
2428       {
2429         p->cost += cost;
2430         p->conflicts += conflicts;
2431         return;
2432       }
2433   p = (struct web_pair *) ra_alloc (sizeof *p);
2434   p->next_hash = web_pair_hash[hash];
2435   p->next_list = web_pair_list;
2436   p->smaller = web1;
2437   p->larger = web2;
2438   p->conflicts = conflicts;
2439   p->cost = cost;
2440   web_pair_hash[hash] = p;
2441   web_pair_list = p;
2442   num_web_pairs++;
2443 }
2444
2445 /* Suitable to be passed to qsort().  Sort web pairs so, that those
2446    with more conflicts and higher cost (which actually is a saving
2447    when the moves are removed) come first.  */
2448
2449 static int
2450 comp_web_pairs (w1, w2)
2451      const void *w1, *w2;
2452 {
2453   struct web_pair *p1 = *(struct web_pair **)w1;
2454   struct web_pair *p2 = *(struct web_pair **)w2;
2455   if (p1->conflicts > p2->conflicts)
2456     return -1;
2457   else if (p1->conflicts < p2->conflicts)
2458     return 1;
2459   else if (p1->cost > p2->cost)
2460     return -1;
2461   else if (p1->cost < p2->cost)
2462     return 1;
2463   else
2464     return 0;
2465 }
2466
2467 /* Given the list of web pairs, begin to combine them from the one
2468    with the most savings.  */
2469
2470 static void
2471 sort_and_combine_web_pairs (for_move)
2472      int for_move;
2473 {
2474   unsigned int i;
2475   struct web_pair **sorted;
2476   struct web_pair *p;
2477   if (!num_web_pairs)
2478     return;
2479   sorted = (struct web_pair **) xmalloc (num_web_pairs * sizeof (sorted[0]));
2480   for (p = web_pair_list, i = 0; p; p = p->next_list)
2481     sorted[i++] = p;
2482   if (i != num_web_pairs)
2483     abort ();
2484   qsort (sorted, num_web_pairs, sizeof (sorted[0]), comp_web_pairs);
2485
2486   /* After combining one pair, we actually should adjust the savings
2487      of the other pairs, if they are connected to one of the just coalesced
2488      pair.  Later.  */
2489   for (i = 0; i < num_web_pairs; i++)
2490     {
2491       struct web *w1, *w2;
2492       p = sorted[i];
2493       w1 = alias (p->smaller);
2494       w2 = alias (p->larger);
2495       if (!for_move && (w1->type == PRECOLORED || w2->type == PRECOLORED))
2496         continue;
2497       else if (w2->type == PRECOLORED)
2498         {
2499           struct web *h = w1;
2500           w1 = w2;
2501           w2 = h;
2502         }
2503       if (w1 != w2
2504           && !TEST_BIT (sup_igraph, w1->id * num_webs + w2->id)
2505           && !TEST_BIT (sup_igraph, w2->id * num_webs + w1->id)
2506           && w2->type != PRECOLORED
2507           && hard_regs_intersect_p (&w1->usable_regs, &w2->usable_regs))
2508           {
2509             if (w1->type != PRECOLORED
2510                 || (w1->type == PRECOLORED && ok (w2, w1)))
2511               combine (w1, w2);
2512             else if (w1->type == PRECOLORED)
2513               SET_HARD_REG_BIT (w2->prefer_colors, w1->color);
2514           }
2515     }
2516   free (sorted);
2517 }
2518
2519 /* Greedily coalesce all moves possible.  Begin with the web pair
2520    giving the most saving if coalesced.  */
2521
2522 static void
2523 aggressive_coalesce ()
2524 {
2525   struct dlist *d;
2526   struct move *m;
2527   init_web_pairs ();
2528   while ((d = pop_list (&mv_worklist)) != NULL)
2529     if ((m = DLIST_MOVE (d)))
2530       {
2531         struct web *s = alias (m->source_web);
2532         struct web *t = alias (m->target_web);
2533         if (t->type == PRECOLORED)
2534           {
2535             struct web *h = s;
2536             s = t;
2537             t = h;
2538           }
2539         if (s != t
2540             && t->type != PRECOLORED
2541             && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
2542             && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
2543           {
2544             if ((s->type == PRECOLORED && ok (t, s))
2545                 || s->type != PRECOLORED)
2546               {
2547                 put_move (m, MV_COALESCED);
2548                 add_web_pair_cost (s, t, BLOCK_FOR_INSN (m->insn)->frequency,
2549                                    0);
2550               }
2551             else if (s->type == PRECOLORED)
2552               /* It is !ok(t, s).  But later when coloring the graph it might
2553                  be possible to take that color.  So we remember the preferred
2554                  color to try that first.  */
2555               {
2556                 put_move (m, CONSTRAINED);
2557                 SET_HARD_REG_BIT (t->prefer_colors, s->color);
2558               }
2559           }
2560         else
2561           {
2562             put_move (m, CONSTRAINED);
2563           }
2564       }
2565   sort_and_combine_web_pairs (1);
2566 }
2567
2568 /* This is the difference between optimistic coalescing and
2569    optimistic coalescing+.  Extended coalesce tries to coalesce also
2570    non-conflicting nodes, not related by a move.  The criteria here is,
2571    the one web must be a source, the other a destination of the same insn.
2572    This actually makes sense, as (because they are in the same insn) they
2573    share many of their neighbors, and if they are coalesced, reduce the
2574    number of conflicts of those neighbors by one.  For this we sort the
2575    candidate pairs again according to savings (and this time also conflict
2576    number).
2577
2578    This is also a comparatively slow operation, as we need to go through
2579    all insns, and for each insn, through all defs and uses.  */
2580
2581 static void
2582 extended_coalesce_2 ()
2583 {
2584   rtx insn;
2585   struct ra_insn_info info;
2586   unsigned int n;
2587   init_web_pairs ();
2588   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2589     if (INSN_P (insn) && (info = insn_df[INSN_UID (insn)]).num_defs)
2590       for (n = 0; n < info.num_defs; n++)
2591         {
2592           struct web *dest = def2web[DF_REF_ID (info.defs[n])];
2593           dest = alias (find_web_for_subweb (dest));
2594           if (dest->type != PRECOLORED && dest->regno < max_normal_pseudo)
2595             {
2596               unsigned int n2;
2597               for (n2 = 0; n2 < info.num_uses; n2++)
2598                 {
2599                   struct web *source = use2web[DF_REF_ID (info.uses[n2])];
2600                   source = alias (find_web_for_subweb (source));
2601                   if (source->type != PRECOLORED
2602                       && source != dest
2603                       && source->regno < max_normal_pseudo
2604                       /* Coalesced webs end up using the same REG rtx in
2605                          emit_colors().  So we can only coalesce something
2606                          of equal modes.  */
2607                       && GET_MODE (source->orig_x) == GET_MODE (dest->orig_x)
2608                       && !TEST_BIT (sup_igraph,
2609                                     dest->id * num_webs + source->id)
2610                       && !TEST_BIT (sup_igraph,
2611                                     source->id * num_webs + dest->id)
2612                       && hard_regs_intersect_p (&source->usable_regs,
2613                                                 &dest->usable_regs))
2614                     add_web_pair_cost (dest, source,
2615                                        BLOCK_FOR_INSN (insn)->frequency,
2616                                        dest->num_conflicts
2617                                        + source->num_conflicts);
2618                 }
2619             }
2620         }
2621   sort_and_combine_web_pairs (0);
2622 }
2623
2624 /* Check if we forgot to coalesce some moves.  */
2625
2626 static void
2627 check_uncoalesced_moves ()
2628 {
2629   struct move_list *ml;
2630   struct move *m;
2631   for (ml = wl_moves; ml; ml = ml->next)
2632     if ((m = ml->move))
2633       {
2634         struct web *s = alias (m->source_web);
2635         struct web *t = alias (m->target_web);
2636         if (t->type == PRECOLORED)
2637           {
2638             struct web *h = s;
2639             s = t;
2640             t = h;
2641           }
2642         if (s != t
2643             && m->type != CONSTRAINED
2644             /* Following can happen when a move was coalesced, but later
2645                broken up again.  Then s!=t, but m is still MV_COALESCED.  */
2646             && m->type != MV_COALESCED
2647             && t->type != PRECOLORED
2648             && ((s->type == PRECOLORED && ok (t, s))
2649                 || s->type != PRECOLORED)
2650             && !TEST_BIT (sup_igraph, s->id * num_webs + t->id)
2651             && !TEST_BIT (sup_igraph, t->id * num_webs + s->id))
2652           abort ();
2653       }
2654 }
2655
2656 /* The toplevel function in this file.  Precondition is, that
2657    the interference graph is built completely by ra-build.c.  This
2658    produces a list of spilled, colored and coalesced nodes.  */
2659
2660 void
2661 ra_colorize_graph (df)
2662      struct df *df;
2663 {
2664   if (rtl_dump_file)
2665     dump_igraph (df);
2666   build_worklists (df);
2667
2668   /* With optimistic coalescing we coalesce everything we can.  */
2669   if (flag_ra_optimistic_coalescing)
2670     {
2671       aggressive_coalesce ();
2672       extended_coalesce_2 ();
2673     }
2674
2675   /* Now build the select stack.  */
2676   do
2677     {
2678       simplify ();
2679       if (mv_worklist)
2680         coalesce ();
2681       else if (WEBS(FREEZE))
2682         freeze ();
2683       else if (WEBS(SPILL))
2684         select_spill ();
2685     }
2686   while (WEBS(SIMPLIFY) || WEBS(SIMPLIFY_FAT) || WEBS(SIMPLIFY_SPILL)
2687          || mv_worklist || WEBS(FREEZE) || WEBS(SPILL));
2688   if (flag_ra_optimistic_coalescing)
2689     check_uncoalesced_moves ();
2690
2691   /* Actually colorize the webs from the select stack.  */
2692   assign_colors ();
2693   check_colors ();
2694   dump_graph_cost (DUMP_COSTS, "initially");
2695   if (flag_ra_break_aliases)
2696     break_coalesced_spills ();
2697   check_colors ();
2698
2699   /* And try to improve the cost by recoloring spilled webs.  */
2700   recolor_spills ();
2701   dump_graph_cost (DUMP_COSTS, "after spill-recolor");
2702   check_colors ();
2703 }
2704
2705 /* Initialize this module.  */
2706
2707 void ra_colorize_init ()
2708 {
2709   /* FIXME: Choose spill heuristic for platform if we have one */
2710   spill_heuristic = default_spill_heuristic;
2711 }
2712
2713 /* Free all memory.  (Note that we don't need to free any per pass
2714    memory).  */
2715
2716 void
2717 ra_colorize_free_all ()
2718 {
2719   struct dlist *d;
2720   while ((d = pop_list (&WEBS(FREE))) != NULL)
2721     put_web (DLIST_WEB (d), INITIAL);
2722   while ((d = pop_list (&WEBS(INITIAL))) != NULL)
2723     {
2724       struct web *web =DLIST_WEB (d);
2725       struct web *wnext;
2726       web->orig_conflict_list = NULL;
2727       web->conflict_list = NULL;
2728       for (web = web->subreg_next; web; web = wnext)
2729         {
2730           wnext = web->subreg_next;
2731           free (web);
2732         }
2733       free (DLIST_WEB (d));
2734     }
2735 }
2736
2737 /*
2738 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
2739 */