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