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       block_stmt_iterator bsi;
 845       tree phi;
 846
 847       /* Start with live on exit temporaries.  */
 848       live_track_init (live, live_on_exit (liveinfo, bb));
 849
 850       for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 851         {
 852           tree var;
 853           tree stmt = bsi_stmt (bsi);
 854
 855           /* A copy between 2 partitions does not introduce an interference
 856              by itself.  If they did, you would never be able to coalesce
 857              two things which are copied.  If the two variables really do
 858              conflict, they will conflict elsewhere in the program.
 859
 860              This is handled by simply removing the SRC of the copy from the
 861              live list, and processing the stmt normally.  */
 862           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 863             {
 864               tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 865               tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 866               if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
 867                 live_track_clear_var (live, rhs);
 868             }
 869
 870           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
 871             live_track_process_def (live, var, graph);
 872
 873           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
 874             live_track_process_use (live, var);
 875         }
 876
 877       /* If result of a PHI is unused, looping over the statements will not
 878          record any conflicts since the def was never live.  Since the PHI node
 879          is going to be translated out of SSA form, it will insert a copy.
 880          There must be a conflict recorded between the result of the PHI and
 881          any variables that are live.  Otherwise the out-of-ssa translation
 882          may create incorrect code.  */
 883       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 884         {
 885           tree result = PHI_RESULT (phi);
 886           if (live_track_live_p (live, result))
 887             live_track_process_def (live, result, graph);
 888         }
 889
 890      live_track_clear_base_vars (live);
 891     }
 892
 893   delete_live_track (live);
 894   return graph;
 895 }
 896
 897
 898 /* Shortcut routine to print messages to file F of the form:
 899    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 900
 901 static inline void
 902 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 903              tree expr2, const char *str3)
 904 {
 905   fprintf (f, "%s", str1);
 906   print_generic_expr (f, expr1, TDF_SLIM);
 907   fprintf (f, "%s", str2);
 908   print_generic_expr (f, expr2, TDF_SLIM);
 909   fprintf (f, "%s", str3);
 910 }
 911
 912
 913 /* Called if a coalesce across and abnormal edge cannot be performed.  PHI is
 914    the phi node at fault, I is the argument index at fault.  A message is
 915    printed and compilation is then terminated.  */
 916
 917 static inline void
 918 abnormal_corrupt (tree phi, int i)
 919 {
 920   edge e = PHI_ARG_EDGE (phi, i);
 921   tree res = PHI_RESULT (phi);
 922   tree arg = PHI_ARG_DEF (phi, i);
 923
 924   fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
 925            e->src->index, e->dest->index);
 926   fprintf (stderr, "Argument %d (", i);
 927   print_generic_expr (stderr, arg, TDF_SLIM);
 928   if (TREE_CODE (arg) != SSA_NAME)
 929     fprintf (stderr, ") is not an SSA_NAME.\n");
 930   else
 931     {
 932       gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
 933       fprintf (stderr, ") does not have the same base variable as the result ");
 934       print_generic_stmt (stderr, res, TDF_SLIM);
 935     }
 936
 937   internal_error ("SSA corruption");
 938 }
 939
 940
 941 /* Print a failure to coalesce a MUST_COALESCE pair X and Y.  */
 942
 943 static inline void
 944 fail_abnormal_edge_coalesce (int x, int y)
 945 {
 946   fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
 947   fprintf (stderr, " which are marked as MUST COALESCE.\n");
 948   print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
 949   fprintf (stderr, " and  ");
 950   print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
 951
 952   internal_error ("SSA corruption");
 953 }
 954
 955
 956 /* This function creates a var_map for the current function as well as creating
 957    a coalesce list for use later in the out of ssa process.  */
 958
 959 static var_map
 960 create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 961 {
 962   block_stmt_iterator bsi;
 963   basic_block bb;
 964   tree var;
 965   tree stmt;
 966   tree first;
 967   var_map map;
 968   ssa_op_iter iter;
 969   int v1, v2, cost;
 970   unsigned i;
 971
 972 #ifdef ENABLE_CHECKING
 973   bitmap used_in_real_ops;
 974   bitmap used_in_virtual_ops;
 975
 976   used_in_real_ops = BITMAP_ALLOC (NULL);
 977   used_in_virtual_ops = BITMAP_ALLOC (NULL);
 978 #endif
 979
 980   map = init_var_map (num_ssa_names + 1);
 981
 982   FOR_EACH_BB (bb)
 983     {
 984       tree phi, arg;
 985
 986       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 987         {
 988           int i;
 989           int ver;
 990           tree res;
 991           bool saw_copy = false;
 992
 993           res = PHI_RESULT (phi);
 994           ver = SSA_NAME_VERSION (res);
 995           register_ssa_partition (map, res);
 996
 997           /* Register ssa_names and coalesces between the args and the result
 998              of all PHI.  */
 999           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1000             {
1001               edge e = PHI_ARG_EDGE (phi, i);
1002               arg = PHI_ARG_DEF (phi, i);
1003               if (TREE_CODE (arg) == SSA_NAME)
1004                 register_ssa_partition (map, arg);
1005               if (TREE_CODE (arg) == SSA_NAME
1006                   && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
1007                 {
1008                   saw_copy = true;
1009                   bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
1010                   if ((e->flags & EDGE_ABNORMAL) == 0)
1011                     {
1012                       int cost = coalesce_cost_edge (e);
1013                       if (cost == 1 && has_single_use (arg))
1014                         add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1015                       else
1016                         add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1017                     }
1018                 }
1019               else
1020                 if (e->flags & EDGE_ABNORMAL)
1021                   abnormal_corrupt (phi, i);
1022             }
1023           if (saw_copy)
1024             bitmap_set_bit (used_in_copy, ver);
1025         }
1026
1027       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1028         {
1029           stmt = bsi_stmt (bsi);
1030
1031           /* Register USE and DEF operands in each statement.  */
1032           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1033             register_ssa_partition (map, var);
1034
1035           /* Check for copy coalesces.  */
1036           switch (TREE_CODE (stmt))
1037             {
1038             case GIMPLE_MODIFY_STMT:
1039               {
1040                 tree op1 = GIMPLE_STMT_OPERAND (stmt, 0);
1041                 tree op2 = GIMPLE_STMT_OPERAND (stmt, 1);
1042                 if (TREE_CODE (op1) == SSA_NAME
1043                     && TREE_CODE (op2) == SSA_NAME
1044                     && SSA_NAME_VAR (op1) == SSA_NAME_VAR (op2))
1045                   {
1046                     v1 = SSA_NAME_VERSION (op1);
1047                     v2 = SSA_NAME_VERSION (op2);
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 ASM_EXPR:
1057               {
1058                 unsigned long noutputs, i;
1059                 tree *outputs, link;
1060                 noutputs = list_length (ASM_OUTPUTS (stmt));
1061                 outputs = (tree *) alloca (noutputs * sizeof (tree));
1062                 for (i = 0, link = ASM_OUTPUTS (stmt); link;
1063                      ++i, link = TREE_CHAIN (link))
1064                   outputs[i] = TREE_VALUE (link);
1065
1066                 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
1067                   {
1068                     const char *constraint
1069                       = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1070                     tree input = TREE_VALUE (link);
1071                     char *end;
1072                     unsigned long match;
1073
1074                     if (TREE_CODE (input) != SSA_NAME)
1075                       continue;
1076
1077                     match = strtoul (constraint, &end, 10);
1078                     if (match >= noutputs || end == constraint)
1079                       continue;
1080
1081                     if (TREE_CODE (outputs[match]) != SSA_NAME)
1082                       continue;
1083
1084                     v1 = SSA_NAME_VERSION (outputs[match]);
1085                     v2 = SSA_NAME_VERSION (input);
1086
1087                     if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
1088                       {
1089                         cost = coalesce_cost (REG_BR_PROB_BASE,
1090                                               maybe_hot_bb_p (bb),
1091                                               false);
1092                         add_coalesce (cl, v1, v2, cost);
1093                         bitmap_set_bit (used_in_copy, v1);
1094                         bitmap_set_bit (used_in_copy, v2);
1095                       }
1096                   }
1097                 break;
1098               }
1099
1100             default:
1101               break;
1102             }
1103
1104 #ifdef ENABLE_CHECKING
1105           /* Mark real uses and defs.  */
1106           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1107             bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
1108
1109           /* Validate that virtual ops don't get used in funny ways.  */
1110           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
1111             {
1112               bitmap_set_bit (used_in_virtual_ops,
1113                               DECL_UID (SSA_NAME_VAR (var)));
1114             }
1115
1116 #endif /* ENABLE_CHECKING */
1117         }
1118     }
1119
1120   /* Now process result decls and live on entry variables for entry into
1121      the coalesce list.  */
1122   first = NULL_TREE;
1123   for (i = 1; i < num_ssa_names; i++)
1124     {
1125       var = map->partition_to_var[i];
1126       if (var != NULL_TREE)
1127         {
1128           /* Add coalesces between all the result decls.  */
1129           if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1130             {
1131               if (first == NULL_TREE)
1132                 first = var;
1133               else
1134                 {
1135                   gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
1136                   v1 = SSA_NAME_VERSION (first);
1137                   v2 = SSA_NAME_VERSION (var);
1138                   bitmap_set_bit (used_in_copy, v1);
1139                   bitmap_set_bit (used_in_copy, v2);
1140                   cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
1141                   add_coalesce (cl, v1, v2, cost);
1142                 }
1143             }
1144           /* Mark any default_def variables as being in the coalesce list
1145              since they will have to be coalesced with the base variable.  If
1146              not marked as present, they won't be in the coalesce view. */
1147           if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
1148             bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1149         }
1150     }
1151
1152 #if defined ENABLE_CHECKING
1153   {
1154     unsigned i;
1155     bitmap both = BITMAP_ALLOC (NULL);
1156     bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
1157     if (!bitmap_empty_p (both))
1158       {
1159         bitmap_iterator bi;
1160
1161         EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
1162           fprintf (stderr, "Variable %s used in real and virtual operands\n",
1163                    get_name (referenced_var (i)));
1164         internal_error ("SSA corruption");
1165       }
1166
1167     BITMAP_FREE (used_in_real_ops);
1168     BITMAP_FREE (used_in_virtual_ops);
1169     BITMAP_FREE (both);
1170   }
1171 #endif
1172
1173   return map;
1174 }
1175
1176
1177 /* Attempt to coalesce ssa versions X and Y together using the partition
1178    mapping in MAP and checking conflicts in GRAPH.  Output any debug info to
1179    DEBUG, if it is nun-NULL.  */
1180
1181 static inline bool
1182 attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
1183                   FILE *debug)
1184 {
1185   int z;
1186   tree var1, var2;
1187   int p1, p2;
1188
1189   p1 = var_to_partition (map, ssa_name (x));
1190   p2 = var_to_partition (map, ssa_name (y));
1191
1192   if (debug)
1193     {
1194       fprintf (debug, "(%d)", x);
1195       print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1196       fprintf (debug, " & (%d)", y);
1197       print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1198     }
1199
1200   if (p1 == p2)
1201     {
1202       if (debug)
1203         fprintf (debug, ": Already Coalesced.\n");
1204       return true;
1205     }
1206
1207   if (debug)
1208     fprintf (debug, " [map: %d, %d] ", p1, p2);
1209
1210
1211   if (!ssa_conflicts_test_p (graph, p1, p2))
1212     {
1213       var1 = partition_to_var (map, p1);
1214       var2 = partition_to_var (map, p2);
1215       z = var_union (map, var1, var2);
1216       if (z == NO_PARTITION)
1217         {
1218           if (debug)
1219             fprintf (debug, ": Unable to perform partition union.\n");
1220           return false;
1221         }
1222
1223       /* z is the new combined partition.  Remove the other partition from
1224          the list, and merge the conflicts.  */
1225       if (z == p1)
1226         ssa_conflicts_merge (graph, p1, p2);
1227       else
1228         ssa_conflicts_merge (graph, p2, p1);
1229
1230       if (debug)
1231         fprintf (debug, ": Success -> %d\n", z);
1232       return true;
1233     }
1234
1235   if (debug)
1236     fprintf (debug, ": Fail due to conflict\n");
1237
1238   return false;
1239 }
1240
1241
1242 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1243    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
1244
1245 static void
1246 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
1247                      FILE *debug)
1248 {
1249   int x = 0, y = 0;
1250   tree var1, var2, phi;
1251   int cost;
1252   basic_block bb;
1253   edge e;
1254   edge_iterator ei;
1255
1256   /* First, coalesce all the copies across abnormal edges.  These are not placed
1257      in the coalesce list because they do not need to be sorted, and simply
1258      consume extra memory/compilation time in large programs.  */
1259
1260   FOR_EACH_BB (bb)
1261     {
1262       FOR_EACH_EDGE (e, ei, bb->preds)
1263         if (e->flags & EDGE_ABNORMAL)
1264           {
1265             for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1266               {
1267                 tree res = PHI_RESULT (phi);
1268                 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1269                 int v1 = SSA_NAME_VERSION (res);
1270                 int v2 = SSA_NAME_VERSION (arg);
1271
1272                 if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
1273                   abnormal_corrupt (phi, e->dest_idx);
1274
1275                 if (debug)
1276                   fprintf (debug, "Abnormal coalesce: ");
1277
1278                 if (!attempt_coalesce (map, graph, v1, v2, debug))
1279                   fail_abnormal_edge_coalesce (v1, v2);
1280               }
1281           }
1282     }
1283
1284   /* Now process the items in the coalesce list.  */
1285
1286   while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1287     {
1288       var1 = ssa_name (x);
1289       var2 = ssa_name (y);
1290
1291       /* Assert the coalesces have the same base variable.  */
1292       gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
1293
1294       if (debug)
1295         fprintf (debug, "Coalesce list: ");
1296       attempt_coalesce (map, graph, x, y, debug);
1297     }
1298 }
1299
1300
1301 /* Reduce the number of copies by coalescing variables in the function.  Return
1302    a partition map with the resulting coalesces.  */
1303
1304 extern var_map
1305 coalesce_ssa_name (void)
1306 {
1307   unsigned num, x;
1308   tree_live_info_p liveinfo;
1309   ssa_conflicts_p graph;
1310   coalesce_list_p cl;
1311   bitmap used_in_copies = BITMAP_ALLOC (NULL);
1312   var_map map;
1313
1314   cl = create_coalesce_list ();
1315   map = create_outofssa_var_map (cl, used_in_copies);
1316
1317   /* Don't calculate live ranges for variables not in the coalesce list.  */
1318   partition_view_bitmap (map, used_in_copies, true);
1319   BITMAP_FREE (used_in_copies);
1320
1321   if (num_var_partitions (map) < 1)
1322     {
1323       delete_coalesce_list (cl);
1324       return map;
1325     }
1326
1327   if (dump_file && (dump_flags & TDF_DETAILS))
1328     dump_var_map (dump_file, map);
1329
1330   liveinfo = calculate_live_ranges (map);
1331
1332   if (dump_file && (dump_flags & TDF_DETAILS))
1333     dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1334
1335   /* Build a conflict graph.  */
1336   graph = build_ssa_conflict_graph (liveinfo);
1337   delete_tree_live_info (liveinfo);
1338   if (dump_file && (dump_flags & TDF_DETAILS))
1339     ssa_conflicts_dump (dump_file, graph);
1340
1341   sort_coalesce_list (cl);
1342
1343   if (dump_file && (dump_flags & TDF_DETAILS))
1344     {
1345       fprintf (dump_file, "\nAfter sorting:\n");
1346       dump_coalesce_list (dump_file, cl);
1347     }
1348
1349   /* First, coalesce all live on entry variables to their base variable.
1350      This will ensure the first use is coming from the correct location.  */
1351
1352   num = num_var_partitions (map);
1353   for (x = 0 ; x < num; x++)
1354     {
1355       tree var = partition_to_var (map, x);
1356       tree root;
1357
1358       if (TREE_CODE (var) != SSA_NAME)
1359         continue;
1360
1361       root = SSA_NAME_VAR (var);
1362       if (gimple_default_def (cfun, root) == var)
1363         {
1364           /* This root variable should have not already been assigned
1365              to another partition which is not coalesced with this one.  */
1366           gcc_assert (!var_ann (root)->out_of_ssa_tag);
1367
1368           if (dump_file && (dump_flags & TDF_DETAILS))
1369             {
1370               print_exprs (dump_file, "Must coalesce ", var,
1371                            " with the root variable ", root, ".\n");
1372             }
1373           change_partition_var (map, root, x);
1374         }
1375     }
1376
1377   if (dump_file && (dump_flags & TDF_DETAILS))
1378     dump_var_map (dump_file, map);
1379
1380   /* Now coalesce everything in the list.  */
1381   coalesce_partitions (map, graph, cl,
1382                        ((dump_flags & TDF_DETAILS) ? dump_file
1383                                                    : NULL));
1384
1385   delete_coalesce_list (cl);
1386   ssa_conflicts_delete (graph);
1387
1388   return map;
1389 }
1390