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