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