gcc/tree-ssa-coalesce.c

   1 /* Coalesce SSA_NAMES together for the out-of-ssa pass.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
   3    Inc.
   4    Contributed by Andrew MacLeod <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "flags.h"
  28 #include "diagnostic.h"
  29 #include "bitmap.h"
  30 #include "tree-flow.h"
  31 #include "hashtab.h"
  32 #include "tree-dump.h"
  33 #include "tree-ssa-live.h"
  34 #include "toplev.h"
  35
  36
  37 /* This set of routines implements a coalesce_list.  This is an object which
  38    is used to track pairs of ssa_names which are desirable to coalesce
  39    together to avoid copies.  Costs are associated with each pair, and when
  40    all desired information has been collected, the object can be used to
  41    order the pairs for processing.  */
  42
  43 /* This structure defines a pair entry.  */
  44
  45 typedef struct coalesce_pair
  46 {
  47   int first_element;
  48   int second_element;
  49   int cost;
  50 } * coalesce_pair_p;
  51 typedef const struct coalesce_pair *const_coalesce_pair_p;
  52
  53 typedef struct cost_one_pair_d
  54 {
  55   int first_element;
  56   int second_element;
  57   struct cost_one_pair_d *next;
  58 } * cost_one_pair_p;
  59
  60 /* This structure maintains the list of coalesce pairs.  */
  61
  62 typedef struct coalesce_list_d
  63 {
  64   htab_t list;                  /* Hash table.  */
  65   coalesce_pair_p *sorted;      /* List when sorted.  */
  66   int num_sorted;               /* Number in the sorted list.  */
  67   cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1.  */
  68 } *coalesce_list_p;
  69
  70 #define NO_BEST_COALESCE        -1
  71 #define MUST_COALESCE_COST      INT_MAX
  72
  73
  74 /* Return cost of execution of copy instruction with FREQUENCY
  75    possibly on CRITICAL edge and in HOT basic block.  */
  76
  77 static inline int
  78 coalesce_cost (int frequency, bool optimize_for_size, bool critical)
  79 {
  80   /* Base costs on BB frequencies bounded by 1.  */
  81   int cost = frequency;
  82
  83   if (!cost)
  84     cost = 1;
  85
  86   if (optimize_for_size)
  87     cost = 1;
  88
  89   /* Inserting copy on critical edge costs more than inserting it elsewhere.  */
  90   if (critical)
  91     cost *= 2;
  92   return cost;
  93 }
  94
  95
  96 /* Return the cost of executing a copy instruction in basic block BB.  */
  97
  98 static inline int
  99 coalesce_cost_bb (basic_block bb)
 100 {
 101   return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb), false);
 102 }
 103
 104
 105 /* Return the cost of executing a copy instruction on edge E.  */
 106
 107 static inline int
 108 coalesce_cost_edge (edge e)
 109 {
 110   if (e->flags & EDGE_ABNORMAL)
 111     return MUST_COALESCE_COST;
 112
 113   return coalesce_cost (EDGE_FREQUENCY (e),
 114                         optimize_edge_for_size_p (e),
 115                         EDGE_CRITICAL_P (e));
 116 }
 117
 118
 119 /* Retrieve a pair to coalesce from the cost_one_list in CL.  Returns the
 120    2 elements via P1 and P2.  1 is returned by the function if there is a pair,
 121    NO_BEST_COALESCE is returned if there aren't any.  */
 122
 123 static inline int
 124 pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2)
 125 {
 126   cost_one_pair_p ptr;
 127
 128   ptr = cl->cost_one_list;
 129   if (!ptr)
 130     return NO_BEST_COALESCE;
 131
 132   *p1 = ptr->first_element;
 133   *p2 = ptr->second_element;
 134   cl->cost_one_list = ptr->next;
 135
 136   free (ptr);
 137
 138   return 1;
 139 }
 140
 141 /* Retrieve the most expensive remaining pair to coalesce from CL.  Returns the
 142    2 elements via P1 and P2.  Their calculated cost is returned by the function.
 143    NO_BEST_COALESCE is returned if the coalesce list is empty.  */
 144
 145 static inline int
 146 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
 147 {
 148   coalesce_pair_p node;
 149   int ret;
 150
 151   if (cl->sorted == NULL)
 152     return pop_cost_one_pair (cl, p1, p2);
 153
 154   if (cl->num_sorted == 0)
 155     return pop_cost_one_pair (cl, p1, p2);
 156
 157   node = cl->sorted[--(cl->num_sorted)];
 158   *p1 = node->first_element;
 159   *p2 = node->second_element;
 160   ret = node->cost;
 161   free (node);
 162
 163   return ret;
 164 }
 165
 166
 167 #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
 168
 169 /* Hash function for coalesce list.  Calculate hash for PAIR.   */
 170
 171 static unsigned int
 172 coalesce_pair_map_hash (const void *pair)
 173 {
 174   hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
 175   hashval_t b = (hashval_t)(((const_coalesce_pair_p)pair)->second_element);
 176
 177   return COALESCE_HASH_FN (a,b);
 178 }
 179
 180
 181 /* Equality function for coalesce list hash table.  Compare PAIR1 and PAIR2,
 182    returning TRUE if the two pairs are equivalent.  */
 183
 184 static int
 185 coalesce_pair_map_eq (const void *pair1, const void *pair2)
 186 {
 187   const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
 188   const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2;
 189
 190   return (p1->first_element == p2->first_element
 191           && p1->second_element == p2->second_element);
 192 }
 193
 194
 195 /* Create a new empty coalesce list object and return it.  */
 196
 197 static inline coalesce_list_p
 198 create_coalesce_list (void)
 199 {
 200   coalesce_list_p list;
 201   unsigned size = num_ssa_names * 3;
 202
 203   if (size < 40)
 204     size = 40;
 205
 206   list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
 207   list->list = htab_create (size, coalesce_pair_map_hash,
 208                             coalesce_pair_map_eq, NULL);
 209   list->sorted = NULL;
 210   list->num_sorted = 0;
 211   list->cost_one_list = NULL;
 212   return list;
 213 }
 214
 215
 216 /* Delete coalesce list CL.  */
 217
 218 static inline void
 219 delete_coalesce_list (coalesce_list_p cl)
 220 {
 221   gcc_assert (cl->cost_one_list == NULL);
 222   htab_delete (cl->list);
 223   if (cl->sorted)
 224     free (cl->sorted);
 225   gcc_assert (cl->num_sorted == 0);
 226   free (cl);
 227 }
 228
 229
 230 /* Find a matching coalesce pair object in CL for the pair P1 and P2.  If
 231    one isn't found, return NULL if CREATE is false, otherwise create a new
 232    coalesce pair object and return it.  */
 233
 234 static coalesce_pair_p
 235 find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
 236 {
 237   struct coalesce_pair p, *pair;
 238   void **slot;
 239   unsigned int hash;
 240
 241   /* Normalize so that p1 is the smaller value.  */
 242   if (p2 < p1)
 243     {
 244       p.first_element = p2;
 245       p.second_element = p1;
 246     }
 247   else
 248     {
 249       p.first_element = p1;
 250       p.second_element = p2;
 251     }
 252
 253
 254   hash = coalesce_pair_map_hash (&p);
 255   pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash);
 256
 257   if (create && !pair)
 258     {
 259       gcc_assert (cl->sorted == NULL);
 260       pair = XNEW (struct coalesce_pair);
 261       pair->first_element = p.first_element;
 262       pair->second_element = p.second_element;
 263       pair->cost = 0;
 264       slot = htab_find_slot_with_hash (cl->list, pair, hash, INSERT);
 265       *(struct coalesce_pair **)slot = pair;
 266     }
 267
 268   return pair;
 269 }
 270
 271 static inline void
 272 add_cost_one_coalesce (coalesce_list_p cl, int p1, int p2)
 273 {
 274   cost_one_pair_p pair;
 275
 276   pair = XNEW (struct cost_one_pair_d);
 277   pair->first_element = p1;
 278   pair->second_element = p2;
 279   pair->next = cl->cost_one_list;
 280   cl->cost_one_list = pair;
 281 }
 282
 283
 284 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE.  */
 285
 286 static inline void
 287 add_coalesce (coalesce_list_p cl, int p1, int p2,
 288               int value)
 289 {
 290   coalesce_pair_p node;
 291
 292   gcc_assert (cl->sorted == NULL);
 293   if (p1 == p2)
 294     return;
 295
 296   node = find_coalesce_pair (cl, p1, p2, true);
 297
 298   /* Once the value is MUST_COALESCE_COST, leave it that way.  */
 299   if (node->cost != MUST_COALESCE_COST)
 300     {
 301       if (value == MUST_COALESCE_COST)
 302         node->cost = value;
 303       else
 304         node->cost += value;
 305     }
 306 }
 307
 308
 309 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order.  */
 310
 311 static int
 312 compare_pairs (const void *p1, const void *p2)
 313 {
 314   const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1;
 315   const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2;
 316   int result;
 317
 318   result = (* pp2)->cost - (* pp1)->cost;
 319   /* Since qsort does not guarantee stability we use the elements
 320      as a secondary key.  This provides us with independence from
 321      the host's implementation of the sorting algorithm.  */
 322   if (result == 0)
 323     {
 324       result = (* pp2)->first_element - (* pp1)->first_element;
 325       if (result == 0)
 326         result = (* pp2)->second_element - (* pp1)->second_element;
 327     }
 328
 329   return result;
 330 }
 331
 332
 333 /* Return the number of unique coalesce pairs in CL.  */
 334
 335 static inline int
 336 num_coalesce_pairs (coalesce_list_p cl)
 337 {
 338   return htab_elements (cl->list);
 339 }
 340
 341
 342 /* Iterator over hash table pairs.  */
 343 typedef struct
 344 {
 345   htab_iterator hti;
 346 } coalesce_pair_iterator;
 347
 348
 349 /* Return first partition pair from list CL, initializing iterator ITER.  */
 350
 351 static inline coalesce_pair_p
 352 first_coalesce_pair (coalesce_list_p cl, coalesce_pair_iterator *iter)
 353 {
 354   coalesce_pair_p pair;
 355
 356   pair = (coalesce_pair_p) first_htab_element (&(iter->hti), cl->list);
 357   return pair;
 358 }
 359
 360
 361 /* Return TRUE if there are no more partitions in for ITER to process.  */
 362
 363 static inline bool
 364 end_coalesce_pair_p (coalesce_pair_iterator *iter)
 365 {
 366   return end_htab_p (&(iter->hti));
 367 }
 368
 369
 370 /* Return the next partition pair to be visited by ITER.  */
 371
 372 static inline coalesce_pair_p
 373 next_coalesce_pair (coalesce_pair_iterator *iter)
 374 {
 375   coalesce_pair_p pair;
 376
 377   pair = (coalesce_pair_p) next_htab_element (&(iter->hti));
 378   return pair;
 379 }
 380
 381
 382 /* Iterate over CL using ITER, returning values in PAIR.  */
 383
 384 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL)         \
 385   for ((PAIR) = first_coalesce_pair ((CL), &(ITER));    \
 386        !end_coalesce_pair_p (&(ITER));                  \
 387        (PAIR) = next_coalesce_pair (&(ITER)))
 388
 389
 390 /* Prepare CL for removal of preferred pairs.  When finished they are sorted
 391    in order from most important coalesce to least important.  */
 392
 393 static void
 394 sort_coalesce_list (coalesce_list_p cl)
 395 {
 396   unsigned x, num;
 397   coalesce_pair_p p;
 398   coalesce_pair_iterator ppi;
 399
 400   gcc_assert (cl->sorted == NULL);
 401
 402   num = num_coalesce_pairs (cl);
 403   cl->num_sorted = num;
 404   if (num == 0)
 405     return;
 406
 407   /* Allocate a vector for the pair pointers.  */
 408   cl->sorted = XNEWVEC (coalesce_pair_p, num);
 409
 410   /* Populate the vector with pointers to the pairs.  */
 411   x = 0;
 412   FOR_EACH_PARTITION_PAIR (p, ppi, cl)
 413     cl->sorted[x++] = p;
 414   gcc_assert (x == num);
 415
 416   /* Already sorted.  */
 417   if (num == 1)
 418     return;
 419
 420   /* If there are only 2, just pick swap them if the order isn't correct.  */
 421   if (num == 2)
 422     {
 423       if (cl->sorted[0]->cost > cl->sorted[1]->cost)
 424         {
 425           p = cl->sorted[0];
 426           cl->sorted[0] = cl->sorted[1];
 427           cl->sorted[1] = p;
 428         }
 429       return;
 430     }
 431
 432   /* Only call qsort if there are more than 2 items.  */
 433   if (num > 2)
 434       qsort (cl->sorted, num, sizeof (coalesce_pair_p), compare_pairs);
 435 }
 436
 437
 438 /* Send debug info for coalesce list CL to file F.  */
 439
 440 static void
 441 dump_coalesce_list (FILE *f, coalesce_list_p cl)
 442 {
 443   coalesce_pair_p node;
 444   coalesce_pair_iterator ppi;
 445   int x;
 446   tree var;
 447
 448   if (cl->sorted == NULL)
 449     {
 450       fprintf (f, "Coalesce List:\n");
 451       FOR_EACH_PARTITION_PAIR (node, ppi, cl)
 452         {
 453           tree var1 = ssa_name (node->first_element);
 454           tree var2 = ssa_name (node->second_element);
 455           print_generic_expr (f, var1, TDF_SLIM);
 456           fprintf (f, " <-> ");
 457           print_generic_expr (f, var2, TDF_SLIM);
 458           fprintf (f, "  (%1d), ", node->cost);
 459           fprintf (f, "\n");
 460         }
 461     }
 462   else
 463     {
 464       fprintf (f, "Sorted Coalesce list:\n");
 465       for (x = cl->num_sorted - 1 ; x >=0; x--)
 466         {
 467           node = cl->sorted[x];
 468           fprintf (f, "(%d) ", node->cost);
 469           var = ssa_name (node->first_element);
 470           print_generic_expr (f, var, TDF_SLIM);
 471           fprintf (f, " <-> ");
 472           var = ssa_name (node->second_element);
 473           print_generic_expr (f, var, TDF_SLIM);
 474           fprintf (f, "\n");
 475         }
 476     }
 477 }
 478
 479
 480 /* This represents a conflict graph.  Implemented as an array of bitmaps.
 481    A full matrix is used for conflicts rather than just upper triangular form.
 482    this make sit much simpler and faster to perform conflict merges.  */
 483
 484 typedef struct ssa_conflicts_d
 485 {
 486   unsigned size;
 487   bitmap *conflicts;
 488 } * ssa_conflicts_p;
 489
 490
 491 /* Return an empty new conflict graph for SIZE elements.  */
 492
 493 static inline ssa_conflicts_p
 494 ssa_conflicts_new (unsigned size)
 495 {
 496   ssa_conflicts_p ptr;
 497
 498   ptr = XNEW (struct ssa_conflicts_d);
 499   ptr->conflicts = XCNEWVEC (bitmap, size);
 500   ptr->size = size;
 501   return ptr;
 502 }
 503
 504
 505 /* Free storage for conflict graph PTR.  */
 506
 507 static inline void
 508 ssa_conflicts_delete (ssa_conflicts_p ptr)
 509 {
 510   unsigned x;
 511   for (x = 0; x < ptr->size; x++)
 512     if (ptr->conflicts[x])
 513       BITMAP_FREE (ptr->conflicts[x]);
 514
 515   free (ptr->conflicts);
 516   free (ptr);
 517 }
 518
 519
 520 /* Test if elements X and Y conflict in graph PTR.  */
 521
 522 static inline bool
 523 ssa_conflicts_test_p (ssa_conflicts_p ptr, unsigned x, unsigned y)
 524 {
 525   bitmap b;
 526
 527 #ifdef ENABLE_CHECKING
 528   gcc_assert (x < ptr->size);
 529   gcc_assert (y < ptr->size);
 530   gcc_assert (x != y);
 531 #endif
 532
 533   b = ptr->conflicts[x];
 534   if (b)
 535     /* Avoid the lookup if Y has no conflicts.  */
 536     return ptr->conflicts[y] ? bitmap_bit_p (b, y) : false;
 537   else
 538     return false;
 539 }
 540
 541
 542 /* Add a conflict with Y to the bitmap for X in graph PTR.  */
 543
 544 static inline void
 545 ssa_conflicts_add_one (ssa_conflicts_p ptr, unsigned x, unsigned y)
 546 {
 547   /* If there are no conflicts yet, allocate the bitmap and set bit.  */
 548   if (!ptr->conflicts[x])
 549     ptr->conflicts[x] = BITMAP_ALLOC (NULL);
 550   bitmap_set_bit (ptr->conflicts[x], y);
 551 }
 552
 553
 554 /* Add conflicts between X and Y in graph PTR.  */
 555
 556 static inline void
 557 ssa_conflicts_add (ssa_conflicts_p ptr, unsigned x, unsigned y)
 558 {
 559 #ifdef ENABLE_CHECKING
 560   gcc_assert (x < ptr->size);
 561   gcc_assert (y < ptr->size);
 562   gcc_assert (x != y);
 563 #endif
 564   ssa_conflicts_add_one (ptr, x, y);
 565   ssa_conflicts_add_one (ptr, y, x);
 566 }
 567
 568
 569 /* Merge all Y's conflict into X in graph PTR.  */
 570
 571 static inline void
 572 ssa_conflicts_merge (ssa_conflicts_p ptr, unsigned x, unsigned y)
 573 {
 574   unsigned z;
 575   bitmap_iterator bi;
 576
 577   gcc_assert (x != y);
 578   if (!(ptr->conflicts[y]))
 579     return;
 580
 581   /* Add a conflict between X and every one Y has.  If the bitmap doesn't
 582      exist, then it has already been coalesced, and we don't need to add a
 583      conflict.  */
 584   EXECUTE_IF_SET_IN_BITMAP (ptr->conflicts[y], 0, z, bi)
 585     if (ptr->conflicts[z])
 586       bitmap_set_bit (ptr->conflicts[z], x);
 587
 588   if (ptr->conflicts[x])
 589     {
 590       /* If X has conflicts, add Y's to X.  */
 591       bitmap_ior_into (ptr->conflicts[x], ptr->conflicts[y]);
 592       BITMAP_FREE (ptr->conflicts[y]);
 593     }
 594   else
 595     {
 596       /* If X has no conflicts, simply use Y's.  */
 597       ptr->conflicts[x] = ptr->conflicts[y];
 598       ptr->conflicts[y] = NULL;
 599     }
 600 }
 601
 602
 603 /* Dump a conflicts graph.  */
 604
 605 static void
 606 ssa_conflicts_dump (FILE *file, ssa_conflicts_p ptr)
 607 {
 608   unsigned x;
 609
 610   fprintf (file, "\nConflict graph:\n");
 611
 612   for (x = 0; x < ptr->size; x++)
 613     if (ptr->conflicts[x])
 614       {
 615         fprintf (dump_file, "%d: ", x);
 616         dump_bitmap (file, ptr->conflicts[x]);
 617       }
 618 }
 619
 620
 621 /* This structure is used to efficiently record the current status of live
 622    SSA_NAMES when building a conflict graph.
 623    LIVE_BASE_VAR has a bit set for each base variable which has at least one
 624    ssa version live.
 625    LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
 626    index, and is used to track what partitions of each base variable are
 627    live.  This makes it easy to add conflicts between just live partitions
 628    with the same base variable.
 629    The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
 630    marked as being live.  This delays clearing of these bitmaps until
 631    they are actually needed again.  */
 632
 633 typedef struct live_track_d
 634 {
 635   bitmap live_base_var;         /* Indicates if a basevar is live.  */
 636   bitmap *live_base_partitions; /* Live partitions for each basevar.  */
 637   var_map map;                  /* Var_map being used for partition mapping.  */
 638 } * live_track_p;
 639
 640
 641 /* This routine will create a new live track structure based on the partitions
 642    in MAP.  */
 643
 644 static live_track_p
 645 new_live_track (var_map map)
 646 {
 647   live_track_p ptr;
 648   int lim, x;
 649
 650   /* Make sure there is a partition view in place.  */
 651   gcc_assert (map->partition_to_base_index != NULL);
 652
 653   ptr = (live_track_p) xmalloc (sizeof (struct live_track_d));
 654   ptr->map = map;
 655   lim = num_basevars (map);
 656   ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim);
 657   ptr->live_base_var = BITMAP_ALLOC (NULL);
 658   for (x = 0; x < lim; x++)
 659     ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL);
 660   return ptr;
 661 }
 662
 663
 664 /* This routine will free the memory associated with PTR.  */
 665
 666 static void
 667 delete_live_track (live_track_p ptr)
 668 {
 669   int x, lim;
 670
 671   lim = num_basevars (ptr->map);
 672   for (x = 0; x < lim; x++)
 673     BITMAP_FREE (ptr->live_base_partitions[x]);
 674   BITMAP_FREE (ptr->live_base_var);
 675   free (ptr->live_base_partitions);
 676   free (ptr);
 677 }
 678
 679
 680 /* This function will remove PARTITION from the live list in PTR.  */
 681
 682 static inline void
 683 live_track_remove_partition (live_track_p ptr, int partition)
 684 {
 685   int root;
 686
 687   root = basevar_index (ptr->map, partition);
 688   bitmap_clear_bit (ptr->live_base_partitions[root], partition);
 689   /* If the element list is empty, make the base variable not live either.  */
 690   if (bitmap_empty_p (ptr->live_base_partitions[root]))
 691     bitmap_clear_bit (ptr->live_base_var, root);
 692 }
 693
 694
 695 /* This function will adds PARTITION to the live list in PTR.  */
 696
 697 static inline void
 698 live_track_add_partition (live_track_p ptr, int partition)
 699 {
 700   int root;
 701
 702   root = basevar_index (ptr->map, partition);
 703   /* If this base var wasn't live before, it is now.  Clear the element list
 704      since it was delayed until needed.  */
 705   if (!bitmap_bit_p (ptr->live_base_var, root))
 706     {
 707       bitmap_set_bit (ptr->live_base_var, root);
 708       bitmap_clear (ptr->live_base_partitions[root]);
 709     }
 710   bitmap_set_bit (ptr->live_base_partitions[root], partition);
 711
 712 }
 713
 714
 715 /* Clear the live bit for VAR in PTR.  */
 716
 717 static inline void
 718 live_track_clear_var (live_track_p ptr, tree var)
 719 {
 720   int p;
 721
 722   p = var_to_partition (ptr->map, var);
 723   if (p != NO_PARTITION)
 724     live_track_remove_partition (ptr, p);
 725 }
 726
 727
 728 /* Return TRUE if VAR is live in PTR.  */
 729
 730 static inline bool
 731 live_track_live_p (live_track_p ptr, tree var)
 732 {
 733   int p, root;
 734
 735   p = var_to_partition (ptr->map, var);
 736   if (p != NO_PARTITION)
 737     {
 738       root = basevar_index (ptr->map, p);
 739       if (bitmap_bit_p (ptr->live_base_var, root))
 740         return bitmap_bit_p (ptr->live_base_partitions[root], p);
 741     }
 742   return false;
 743 }
 744
 745
 746 /* This routine will add USE to PTR.  USE will be marked as live in both the
 747    ssa live map and the live bitmap for the root of USE.  */
 748
 749 static inline void
 750 live_track_process_use (live_track_p ptr, tree use)
 751 {
 752   int p;
 753
 754   p = var_to_partition (ptr->map, use);
 755   if (p == NO_PARTITION)
 756     return;
 757
 758   /* Mark as live in the appropriate live list.  */
 759   live_track_add_partition (ptr, p);
 760 }
 761
 762
 763 /* This routine will process a DEF in PTR.  DEF will be removed from the live
 764    lists, and if there are any other live partitions with the same base
 765    variable, conflicts will be added to GRAPH.  */
 766
 767 static inline void
 768 live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
 769 {
 770   int p, root;
 771   bitmap b;
 772   unsigned x;
 773   bitmap_iterator bi;
 774
 775   p = var_to_partition (ptr->map, def);
 776   if (p == NO_PARTITION)
 777     return;
 778
 779   /* Clear the liveness bit.  */
 780   live_track_remove_partition (ptr, p);
 781
 782   /* If the bitmap isn't empty now, conflicts need to be added.  */
 783   root = basevar_index (ptr->map, p);
 784   if (bitmap_bit_p (ptr->live_base_var, root))
 785     {
 786       b = ptr->live_base_partitions[root];
 787       EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
 788         ssa_conflicts_add (graph, p, x);
 789     }
 790 }
 791
 792
 793 /* Initialize PTR with the partitions set in INIT.  */
 794
 795 static inline void
 796 live_track_init (live_track_p ptr, bitmap init)
 797 {
 798   unsigned p;
 799   bitmap_iterator bi;
 800
 801   /* Mark all live on exit partitions.  */
 802   EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
 803     live_track_add_partition (ptr, p);
 804 }
 805
 806
 807 /* This routine will clear all live partitions in PTR.   */
 808
 809 static inline void
 810 live_track_clear_base_vars (live_track_p ptr)
 811 {
 812   /* Simply clear the live base list.  Anything marked as live in the element
 813      lists will be cleared later if/when the base variable ever comes alive
 814      again.  */
 815   bitmap_clear (ptr->live_base_var);
 816 }
 817
 818
 819 /* Build a conflict graph based on LIVEINFO.  Any partitions which are in the
 820    partition view of the var_map liveinfo is based on get entries in the
 821    conflict graph.  Only conflicts between ssa_name partitions with the same
 822    base variable are added.  */
 823
 824 static ssa_conflicts_p
 825 build_ssa_conflict_graph (tree_live_info_p liveinfo)
 826 {
 827   ssa_conflicts_p graph;
 828   var_map map;
 829   basic_block bb;
 830   ssa_op_iter iter;
 831   live_track_p live;
 832
 833   map = live_var_map (liveinfo);
 834   graph = ssa_conflicts_new (num_var_partitions (map));
 835
 836   live = new_live_track (map);
 837
 838   FOR_EACH_BB (bb)
 839     {
 840       gimple_stmt_iterator gsi;
 841
 842       /* Start with live on exit temporaries.  */
 843       live_track_init (live, live_on_exit (liveinfo, bb));
 844
 845       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 846         {
 847           tree var;
 848           gimple stmt = gsi_stmt (gsi);
 849
 850           /* A copy between 2 partitions does not introduce an interference
 851              by itself.  If they did, you would never be able to coalesce
 852              two things which are copied.  If the two variables really do
 853              conflict, they will conflict elsewhere in the program.
 854
 855              This is handled by simply removing the SRC of the copy from the
 856              live list, and processing the stmt normally.  */
 857           if (is_gimple_assign (stmt))
 858             {
 859               tree lhs = gimple_assign_lhs (stmt);
 860               tree rhs1 = gimple_assign_rhs1 (stmt);
 861               if (gimple_assign_copy_p (stmt)
 862                   && TREE_CODE (lhs) == SSA_NAME
 863                   && TREE_CODE (rhs1) == SSA_NAME)
 864                 live_track_clear_var (live, rhs1);
 865             }
 866
 867           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
 868             live_track_process_def (live, var, graph);
 869
 870           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
 871             live_track_process_use (live, var);
 872         }
 873
 874       /* If result of a PHI is unused, looping over the statements will not
 875          record any conflicts since the def was never live.  Since the PHI node
 876          is going to be translated out of SSA form, it will insert a copy.
 877          There must be a conflict recorded between the result of the PHI and
 878          any variables that are live.  Otherwise the out-of-ssa translation
 879          may create incorrect code.  */
 880       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 881         {
 882           gimple phi = gsi_stmt (gsi);
 883           tree result = PHI_RESULT (phi);
 884           if (live_track_live_p (live, result))
 885             live_track_process_def (live, result, graph);
 886         }
 887
 888      live_track_clear_base_vars (live);
 889     }
 890
 891   delete_live_track (live);
 892   return graph;
 893 }
 894
 895
 896 /* Shortcut routine to print messages to file F of the form:
 897    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 898
 899 static inline void
 900 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 901              tree expr2, const char *str3)
 902 {
 903   fprintf (f, "%s", str1);
 904   print_generic_expr (f, expr1, TDF_SLIM);
 905   fprintf (f, "%s", str2);
 906   print_generic_expr (f, expr2, TDF_SLIM);
 907   fprintf (f, "%s", str3);
 908 }
 909
 910
 911 /* Called if a coalesce across and abnormal edge cannot be performed.  PHI is
 912    the phi node at fault, I is the argument index at fault.  A message is
 913    printed and compilation is then terminated.  */
 914
 915 static inline void
 916 abnormal_corrupt (gimple phi, int i)
 917 {
 918   edge e = gimple_phi_arg_edge (phi, i);
 919   tree res = gimple_phi_result (phi);
 920   tree arg = gimple_phi_arg_def (phi, i);
 921
 922   fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
 923            e->src->index, e->dest->index);
 924   fprintf (stderr, "Argument %d (", i);
 925   print_generic_expr (stderr, arg, TDF_SLIM);
 926   if (TREE_CODE (arg) != SSA_NAME)
 927     fprintf (stderr, ") is not an SSA_NAME.\n");
 928   else
 929     {
 930       gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
 931       fprintf (stderr, ") does not have the same base variable as the result ");
 932       print_generic_stmt (stderr, res, TDF_SLIM);
 933     }
 934
 935   internal_error ("SSA corruption");
 936 }
 937
 938
 939 /* Print a failure to coalesce a MUST_COALESCE pair X and Y.  */
 940
 941 static inline void
 942 fail_abnormal_edge_coalesce (int x, int y)
 943 {
 944   fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
 945   fprintf (stderr, " which are marked as MUST COALESCE.\n");
 946   print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
 947   fprintf (stderr, " and  ");
 948   print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
 949
 950   internal_error ("SSA corruption");
 951 }
 952
 953
 954 /* This function creates a var_map for the current function as well as creating
 955    a coalesce list for use later in the out of ssa process.  */
 956
 957 static var_map
 958 create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 959 {
 960   gimple_stmt_iterator gsi;
 961   basic_block bb;
 962   tree var;
 963   gimple stmt;
 964   tree first;
 965   var_map map;
 966   ssa_op_iter iter;
 967   int v1, v2, cost;
 968   unsigned i;
 969
 970 #ifdef ENABLE_CHECKING
 971   bitmap used_in_real_ops;
 972   bitmap used_in_virtual_ops;
 973
 974   used_in_real_ops = BITMAP_ALLOC (NULL);
 975   used_in_virtual_ops = BITMAP_ALLOC (NULL);
 976 #endif
 977
 978   map = init_var_map (num_ssa_names + 1);
 979
 980   FOR_EACH_BB (bb)
 981     {
 982       tree arg;
 983
 984       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 985         {
 986           gimple phi = gsi_stmt (gsi);
 987           size_t i;
 988           int ver;
 989           tree res;
 990           bool saw_copy = false;
 991
 992           res = gimple_phi_result (phi);
 993           ver = SSA_NAME_VERSION (res);
 994           register_ssa_partition (map, res);
 995
 996           /* Register ssa_names and coalesces between the args and the result
 997              of all PHI.  */
 998           for (i = 0; i < gimple_phi_num_args (phi); i++)
 999             {
1000               edge e = gimple_phi_arg_edge (phi, i);
1001               arg = PHI_ARG_DEF (phi, i);
1002               if (TREE_CODE (arg) == SSA_NAME)
1003                 register_ssa_partition (map, arg);
1004               if (TREE_CODE (arg) == SSA_NAME
1005                   && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
1006                 {
1007                   saw_copy = true;
1008                   bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1009                   if ((e->flags & EDGE_ABNORMAL) == 0)
1010                     {
1011                       int cost = coalesce_cost_edge (e);
1012                       if (cost == 1 && has_single_use (arg))
1013                         add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1014                       else
1015                         add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1016                     }
1017                 }
1018               else
1019                 if (e->flags & EDGE_ABNORMAL)
1020                   abnormal_corrupt (phi, i);
1021             }
1022           if (saw_copy)
1023             bitmap_set_bit (used_in_copy, ver);
1024         }
1025
1026       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1027         {
1028           stmt = gsi_stmt (gsi);
1029
1030           /* Register USE and DEF operands in each statement.  */
1031           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1032             register_ssa_partition (map, var);
1033
1034           /* Check for copy coalesces.  */
1035           switch (gimple_code (stmt))
1036             {
1037             case GIMPLE_ASSIGN:
1038               {
1039                 tree lhs = gimple_assign_lhs (stmt);
1040                 tree rhs1 = gimple_assign_rhs1 (stmt);
1041
1042                 if (gimple_assign_copy_p (stmt)
1043                     && TREE_CODE (lhs) == SSA_NAME
1044                     && TREE_CODE (rhs1) == SSA_NAME
1045                     && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1))
1046                   {
1047                     v1 = SSA_NAME_VERSION (lhs);
1048                     v2 = SSA_NAME_VERSION (rhs1);
1049                     cost = coalesce_cost_bb (bb);
1050                     add_coalesce (cl, v1, v2, cost);
1051                     bitmap_set_bit (used_in_copy, v1);
1052                     bitmap_set_bit (used_in_copy, v2);
1053                   }
1054               }
1055               break;
1056
1057             case GIMPLE_ASM:
1058               {
1059                 unsigned long noutputs, i;
1060                 unsigned long ninputs;
1061                 tree *outputs, link;
1062                 noutputs = gimple_asm_noutputs (stmt);
1063                 ninputs = gimple_asm_ninputs (stmt);
1064                 outputs = (tree *) alloca (noutputs * sizeof (tree));
1065                 for (i = 0; i < noutputs; ++i) {
1066                   link = gimple_asm_output_op (stmt, i);
1067                   outputs[i] = TREE_VALUE (link);
1068                 }
1069
1070                 for (i = 0; i < ninputs; ++i)
1071                   {
1072                     const char *constraint;
1073                     tree input;
1074                     char *end;
1075                     unsigned long match;
1076
1077                     link = gimple_asm_input_op (stmt, i);
1078                     constraint
1079                       = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1080                     input = TREE_VALUE (link);
1081
1082                     if (TREE_CODE (input) != SSA_NAME)
1083                       continue;
1084
1085                     match = strtoul (constraint, &end, 10);
1086                     if (match >= noutputs || end == constraint)
1087                       continue;
1088
1089                     if (TREE_CODE (outputs[match]) != SSA_NAME)
1090                       continue;
1091
1092                     v1 = SSA_NAME_VERSION (outputs[match]);
1093                     v2 = SSA_NAME_VERSION (input);
1094
1095                     if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
1096                       {
1097                         cost = coalesce_cost (REG_BR_PROB_BASE,
1098                                               optimize_bb_for_size_p (bb),
1099                                               false);
1100                         add_coalesce (cl, v1, v2, cost);
1101                         bitmap_set_bit (used_in_copy, v1);
1102                         bitmap_set_bit (used_in_copy, v2);
1103                       }
1104                   }
1105                 break;
1106               }
1107
1108             default:
1109               break;
1110             }
1111
1112 #ifdef ENABLE_CHECKING
1113           /* Mark real uses and defs.  */
1114           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1115             bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
1116
1117           /* Validate that virtual ops don't get used in funny ways.  */
1118           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
1119             {
1120               bitmap_set_bit (used_in_virtual_ops,
1121                               DECL_UID (SSA_NAME_VAR (var)));
1122             }
1123
1124 #endif /* ENABLE_CHECKING */
1125         }
1126     }
1127
1128   /* Now process result decls and live on entry variables for entry into
1129      the coalesce list.  */
1130   first = NULL_TREE;
1131   for (i = 1; i < num_ssa_names; i++)
1132     {
1133       var = map->partition_to_var[i];
1134       if (var != NULL_TREE)
1135         {
1136           /* Add coalesces between all the result decls.  */
1137           if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1138             {
1139               if (first == NULL_TREE)
1140                 first = var;
1141               else
1142                 {
1143                   gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
1144                   v1 = SSA_NAME_VERSION (first);
1145                   v2 = SSA_NAME_VERSION (var);
1146                   bitmap_set_bit (used_in_copy, v1);
1147                   bitmap_set_bit (used_in_copy, v2);
1148                   cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
1149                   add_coalesce (cl, v1, v2, cost);
1150                 }
1151             }
1152           /* Mark any default_def variables as being in the coalesce list
1153              since they will have to be coalesced with the base variable.  If
1154              not marked as present, they won't be in the coalesce view. */
1155           if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
1156             bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1157         }
1158     }
1159
1160 #if defined ENABLE_CHECKING
1161   {
1162     unsigned i;
1163     bitmap both = BITMAP_ALLOC (NULL);
1164     bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
1165     if (!bitmap_empty_p (both))
1166       {
1167         bitmap_iterator bi;
1168
1169         EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
1170           fprintf (stderr, "Variable %s used in real and virtual operands\n",
1171                    get_name (referenced_var (i)));
1172         internal_error ("SSA corruption");
1173       }
1174
1175     BITMAP_FREE (used_in_real_ops);
1176     BITMAP_FREE (used_in_virtual_ops);
1177     BITMAP_FREE (both);
1178   }
1179 #endif
1180
1181   return map;
1182 }
1183
1184
1185 /* Attempt to coalesce ssa versions X and Y together using the partition
1186    mapping in MAP and checking conflicts in GRAPH.  Output any debug info to
1187    DEBUG, if it is nun-NULL.  */
1188
1189 static inline bool
1190 attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
1191                   FILE *debug)
1192 {
1193   int z;
1194   tree var1, var2;
1195   int p1, p2;
1196
1197   p1 = var_to_partition (map, ssa_name (x));
1198   p2 = var_to_partition (map, ssa_name (y));
1199
1200   if (debug)
1201     {
1202       fprintf (debug, "(%d)", x);
1203       print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1204       fprintf (debug, " & (%d)", y);
1205       print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1206     }
1207
1208   if (p1 == p2)
1209     {
1210       if (debug)
1211         fprintf (debug, ": Already Coalesced.\n");
1212       return true;
1213     }
1214
1215   if (debug)
1216     fprintf (debug, " [map: %d, %d] ", p1, p2);
1217
1218
1219   if (!ssa_conflicts_test_p (graph, p1, p2))
1220     {
1221       var1 = partition_to_var (map, p1);
1222       var2 = partition_to_var (map, p2);
1223       z = var_union (map, var1, var2);
1224       if (z == NO_PARTITION)
1225         {
1226           if (debug)
1227             fprintf (debug, ": Unable to perform partition union.\n");
1228           return false;
1229         }
1230
1231       /* z is the new combined partition.  Remove the other partition from
1232          the list, and merge the conflicts.  */
1233       if (z == p1)
1234         ssa_conflicts_merge (graph, p1, p2);
1235       else
1236         ssa_conflicts_merge (graph, p2, p1);
1237
1238       if (debug)
1239         fprintf (debug, ": Success -> %d\n", z);
1240       return true;
1241     }
1242
1243   if (debug)
1244     fprintf (debug, ": Fail due to conflict\n");
1245
1246   return false;
1247 }
1248
1249
1250 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1251    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
1252
1253 static void
1254 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
1255                      FILE *debug)
1256 {
1257   int x = 0, y = 0;
1258   tree var1, var2;
1259   int cost;
1260   basic_block bb;
1261   edge e;
1262   edge_iterator ei;
1263
1264   /* First, coalesce all the copies across abnormal edges.  These are not placed
1265      in the coalesce list because they do not need to be sorted, and simply
1266      consume extra memory/compilation time in large programs.  */
1267
1268   FOR_EACH_BB (bb)
1269     {
1270       FOR_EACH_EDGE (e, ei, bb->preds)
1271         if (e->flags & EDGE_ABNORMAL)
1272           {
1273             gimple_stmt_iterator gsi;
1274             for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1275                  gsi_next (&gsi))
1276               {
1277                 gimple phi = gsi_stmt (gsi);
1278                 tree res = PHI_RESULT (phi);
1279                 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1280                 int v1 = SSA_NAME_VERSION (res);
1281                 int v2 = SSA_NAME_VERSION (arg);
1282
1283                 if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
1284                   abnormal_corrupt (phi, e->dest_idx);
1285
1286                 if (debug)
1287                   fprintf (debug, "Abnormal coalesce: ");
1288
1289                 if (!attempt_coalesce (map, graph, v1, v2, debug))
1290                   fail_abnormal_edge_coalesce (v1, v2);
1291               }
1292           }
1293     }
1294
1295   /* Now process the items in the coalesce list.  */
1296
1297   while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1298     {
1299       var1 = ssa_name (x);
1300       var2 = ssa_name (y);
1301
1302       /* Assert the coalesces have the same base variable.  */
1303       gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
1304
1305       if (debug)
1306         fprintf (debug, "Coalesce list: ");
1307       attempt_coalesce (map, graph, x, y, debug);
1308     }
1309 }
1310
1311 /* Returns a hash code for P.  */
1312
1313 static hashval_t
1314 hash_ssa_name_by_var (const void *p)
1315 {
1316   const_tree n = (const_tree) p;
1317   return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
1318 }
1319
1320 /* Returns nonzero if P1 and P2 are equal.  */
1321
1322 static int
1323 eq_ssa_name_by_var (const void *p1, const void *p2)
1324 {
1325   const_tree n1 = (const_tree) p1;
1326   const_tree n2 = (const_tree) p2;
1327   return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
1328 }
1329
1330 /* Reduce the number of copies by coalescing variables in the function.  Return
1331    a partition map with the resulting coalesces.  */
1332
1333 extern var_map
1334 coalesce_ssa_name (void)
1335 {
1336   unsigned num, x;
1337   tree_live_info_p liveinfo;
1338   ssa_conflicts_p graph;
1339   coalesce_list_p cl;
1340   bitmap used_in_copies = BITMAP_ALLOC (NULL);
1341   var_map map;
1342   unsigned int i;
1343   static htab_t ssa_name_hash;
1344
1345   cl = create_coalesce_list ();
1346   map = create_outofssa_var_map (cl, used_in_copies);
1347
1348   /* We need to coalesce all names originating same SSA_NAME_VAR
1349      so debug info remains undisturbed.  */
1350   if (!optimize)
1351     {
1352       ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
1353                                    eq_ssa_name_by_var, NULL);
1354       for (i = 1; i < num_ssa_names; i++)
1355         {
1356           tree a = ssa_name (i);
1357
1358           if (a && SSA_NAME_VAR (a) && !DECL_ARTIFICIAL (SSA_NAME_VAR (a)))
1359             {
1360               tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
1361
1362               if (!*slot)
1363                 *slot = a;
1364               else
1365                 {
1366                   add_coalesce (cl, SSA_NAME_VERSION (a), SSA_NAME_VERSION (*slot),
1367                                 MUST_COALESCE_COST - 1);
1368                   bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
1369                   bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
1370                 }
1371             }
1372         }
1373       htab_delete (ssa_name_hash);
1374     }
1375   if (dump_file && (dump_flags & TDF_DETAILS))
1376     dump_var_map (dump_file, map);
1377
1378   /* Don't calculate live ranges for variables not in the coalesce list.  */
1379   partition_view_bitmap (map, used_in_copies, true);
1380   BITMAP_FREE (used_in_copies);
1381
1382   if (num_var_partitions (map) < 1)
1383     {
1384       delete_coalesce_list (cl);
1385       return map;
1386     }
1387
1388   if (dump_file && (dump_flags & TDF_DETAILS))
1389     dump_var_map (dump_file, map);
1390
1391   liveinfo = calculate_live_ranges (map);
1392
1393   if (dump_file && (dump_flags & TDF_DETAILS))
1394     dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1395
1396   /* Build a conflict graph.  */
1397   graph = build_ssa_conflict_graph (liveinfo);
1398   delete_tree_live_info (liveinfo);
1399   if (dump_file && (dump_flags & TDF_DETAILS))
1400     ssa_conflicts_dump (dump_file, graph);
1401
1402   sort_coalesce_list (cl);
1403
1404   if (dump_file && (dump_flags & TDF_DETAILS))
1405     {
1406       fprintf (dump_file, "\nAfter sorting:\n");
1407       dump_coalesce_list (dump_file, cl);
1408     }
1409
1410   /* First, coalesce all live on entry variables to their base variable.
1411      This will ensure the first use is coming from the correct location.  */
1412
1413   num = num_var_partitions (map);
1414   for (x = 0 ; x < num; x++)
1415     {
1416       tree var = partition_to_var (map, x);
1417       tree root;
1418
1419       if (TREE_CODE (var) != SSA_NAME)
1420         continue;
1421
1422       root = SSA_NAME_VAR (var);
1423       if (gimple_default_def (cfun, root) == var)
1424         {
1425           /* This root variable should have not already been assigned
1426              to another partition which is not coalesced with this one.  */
1427           gcc_assert (!var_ann (root)->out_of_ssa_tag);
1428
1429           if (dump_file && (dump_flags & TDF_DETAILS))
1430             {
1431               print_exprs (dump_file, "Must coalesce ", var,
1432                            " with the root variable ", root, ".\n");
1433             }
1434           change_partition_var (map, root, x);
1435         }
1436     }
1437
1438   if (dump_file && (dump_flags & TDF_DETAILS))
1439     dump_var_map (dump_file, map);
1440
1441   /* Now coalesce everything in the list.  */
1442   coalesce_partitions (map, graph, cl,
1443                        ((dump_flags & TDF_DETAILS) ? dump_file
1444                                                    : NULL));
1445
1446   delete_coalesce_list (cl);
1447   ssa_conflicts_delete (graph);
1448
1449   return map;
1450 }