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