gcc/tree-ssa-coalesce.c

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