contrib/gcc-4.4/gcc/tree-ssa-coalesce.c

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