gcc/tree-ssa-coalesce.c

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