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 /* Dump a conflicts graph.  */
 593
 594 static void
 595 ssa_conflicts_dump (FILE *file, ssa_conflicts_p ptr)
 596 {
 597   unsigned x;
 598
 599   fprintf (file, "\nConflict graph:\n");
 600
 601   for (x = 0; x < ptr->size; x++)
 602     if (ptr->conflicts[x])
 603       {
 604         fprintf (dump_file, "%d: ", x);
 605         dump_bitmap (file, ptr->conflicts[x]);
 606       }
 607 }
 608
 609
 610 /* This structure is used to efficiently record the current status of live
 611    SSA_NAMES when building a conflict graph.
 612    LIVE_BASE_VAR has a bit set for each base variable which has at least one
 613    ssa version live.
 614    LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
 615    index, and is used to track what partitions of each base variable are
 616    live.  This makes it easy to add conflicts between just live partitions
 617    with the same base variable.
 618    The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
 619    marked as being live.  This delays clearing of these bitmaps until
 620    they are actually needed again.  */
 621
 622 typedef struct live_track_d
 623 {
 624   bitmap live_base_var;         /* Indicates if a basevar is live.  */
 625   bitmap *live_base_partitions; /* Live partitions for each basevar.  */
 626   var_map map;                  /* Var_map being used for partition mapping.  */
 627 } * live_track_p;
 628
 629
 630 /* This routine will create a new live track structure based on the partitions
 631    in MAP.  */
 632
 633 static live_track_p
 634 new_live_track (var_map map)
 635 {
 636   live_track_p ptr;
 637   int lim, x;
 638
 639   /* Make sure there is a partition view in place.  */
 640   gcc_assert (map->partition_to_base_index != NULL);
 641
 642   ptr = (live_track_p) xmalloc (sizeof (struct live_track_d));
 643   ptr->map = map;
 644   lim = num_basevars (map);
 645   ptr->live_base_partitions = (bitmap *) xmalloc(sizeof (bitmap *) * lim);
 646   ptr->live_base_var = BITMAP_ALLOC (NULL);
 647   for (x = 0; x < lim; x++)
 648     ptr->live_base_partitions[x] = BITMAP_ALLOC (NULL);
 649   return ptr;
 650 }
 651
 652
 653 /* This routine will free the memory associated with PTR.  */
 654
 655 static void
 656 delete_live_track (live_track_p ptr)
 657 {
 658   int x, lim;
 659
 660   lim = num_basevars (ptr->map);
 661   for (x = 0; x < lim; x++)
 662     BITMAP_FREE (ptr->live_base_partitions[x]);
 663   BITMAP_FREE (ptr->live_base_var);
 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_bit_p (ptr->live_base_var, root))
 695     {
 696       bitmap_set_bit (ptr->live_base_var, root);
 697       bitmap_clear (ptr->live_base_partitions[root]);
 698     }
 699   bitmap_set_bit (ptr->live_base_partitions[root], partition);
 700
 701 }
 702
 703
 704 /* Clear the live bit for VAR in PTR.  */
 705
 706 static inline void
 707 live_track_clear_var (live_track_p ptr, tree var)
 708 {
 709   int p;
 710
 711   p = var_to_partition (ptr->map, var);
 712   if (p != NO_PARTITION)
 713     live_track_remove_partition (ptr, p);
 714 }
 715
 716
 717 /* Return TRUE if VAR is live in PTR.  */
 718
 719 static inline bool
 720 live_track_live_p (live_track_p ptr, tree var)
 721 {
 722   int p, root;
 723
 724   p = var_to_partition (ptr->map, var);
 725   if (p != NO_PARTITION)
 726     {
 727       root = basevar_index (ptr->map, p);
 728       if (bitmap_bit_p (ptr->live_base_var, root))
 729         return bitmap_bit_p (ptr->live_base_partitions[root], p);
 730     }
 731   return false;
 732 }
 733
 734
 735 /* This routine will add USE to PTR.  USE will be marked as live in both the
 736    ssa live map and the live bitmap for the root of USE.  */
 737
 738 static inline void
 739 live_track_process_use (live_track_p ptr, tree use)
 740 {
 741   int p;
 742
 743   p = var_to_partition (ptr->map, use);
 744   if (p == NO_PARTITION)
 745     return;
 746
 747   /* Mark as live in the appropriate live list.  */
 748   live_track_add_partition (ptr, p);
 749 }
 750
 751
 752 /* This routine will process a DEF in PTR.  DEF will be removed from the live
 753    lists, and if there are any other live partitions with the same base
 754    variable, conflicts will be added to GRAPH.  */
 755
 756 static inline void
 757 live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
 758 {
 759   int p, root;
 760   bitmap b;
 761   unsigned x;
 762   bitmap_iterator bi;
 763
 764   p = var_to_partition (ptr->map, def);
 765   if (p == NO_PARTITION)
 766     return;
 767
 768   /* Clear the liveness bit.  */
 769   live_track_remove_partition (ptr, p);
 770
 771   /* If the bitmap isn't empty now, conflicts need to be added.  */
 772   root = basevar_index (ptr->map, p);
 773   if (bitmap_bit_p (ptr->live_base_var, root))
 774     {
 775       b = ptr->live_base_partitions[root];
 776       EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
 777         ssa_conflicts_add (graph, p, x);
 778     }
 779 }
 780
 781
 782 /* Initialize PTR with the partitions set in INIT.  */
 783
 784 static inline void
 785 live_track_init (live_track_p ptr, bitmap init)
 786 {
 787   unsigned p;
 788   bitmap_iterator bi;
 789
 790   /* Mark all live on exit partitions.  */
 791   EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi)
 792     live_track_add_partition (ptr, p);
 793 }
 794
 795
 796 /* This routine will clear all live partitions in PTR.   */
 797
 798 static inline void
 799 live_track_clear_base_vars (live_track_p ptr)
 800 {
 801   /* Simply clear the live base list.  Anything marked as live in the element
 802      lists will be cleared later if/when the base variable ever comes alive
 803      again.  */
 804   bitmap_clear (ptr->live_base_var);
 805 }
 806
 807
 808 /* Build a conflict graph based on LIVEINFO.  Any partitions which are in the
 809    partition view of the var_map liveinfo is based on get entries in the
 810    conflict graph.  Only conflicts between ssa_name partitions with the same
 811    base variable are added.  */
 812
 813 static ssa_conflicts_p
 814 build_ssa_conflict_graph (tree_live_info_p liveinfo)
 815 {
 816   ssa_conflicts_p graph;
 817   var_map map;
 818   basic_block bb;
 819   ssa_op_iter iter;
 820   live_track_p live;
 821
 822   map = live_var_map (liveinfo);
 823   graph = ssa_conflicts_new (num_var_partitions (map));
 824
 825   live = new_live_track (map);
 826
 827   FOR_EACH_BB (bb)
 828     {
 829       block_stmt_iterator bsi;
 830       tree phi;
 831
 832       /* Start with live on exit temporaries.  */
 833       live_track_init (live, live_on_exit (liveinfo, bb));
 834
 835       for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
 836         {
 837           tree var;
 838           tree stmt = bsi_stmt (bsi);
 839
 840           /* A copy between 2 partitions does not introduce an interference
 841              by itself.  If they did, you would never be able to coalesce
 842              two things which are copied.  If the two variables really do
 843              conflict, they will conflict elsewhere in the program.
 844
 845              This is handled by simply removing the SRC of the copy from the
 846              live list, and processing the stmt normally.  */
 847           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 848             {
 849               tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 850               tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 851               if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
 852                 live_track_clear_var (live, rhs);
 853             }
 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 (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 869         {
 870           tree result = PHI_RESULT (phi);
 871           if (live_track_live_p (live, result))
 872             live_track_process_def (live, result, graph);
 873         }
 874
 875      live_track_clear_base_vars (live);
 876     }
 877
 878   delete_live_track (live);
 879   return graph;
 880 }
 881
 882
 883 /* Shortcut routine to print messages to file F of the form:
 884    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 885
 886 static inline void
 887 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 888              tree expr2, const char *str3)
 889 {
 890   fprintf (f, "%s", str1);
 891   print_generic_expr (f, expr1, TDF_SLIM);
 892   fprintf (f, "%s", str2);
 893   print_generic_expr (f, expr2, TDF_SLIM);
 894   fprintf (f, "%s", str3);
 895 }
 896
 897
 898 /* Called if a coalesce across and abnormal edge cannot be performed.  PHI is
 899    the phi node at fault, I is the argument index at fault.  A message is
 900    printed and compilation is then terminated.  */
 901
 902 static inline void
 903 abnormal_corrupt (tree phi, int i)
 904 {
 905   edge e = PHI_ARG_EDGE (phi, i);
 906   tree res = PHI_RESULT (phi);
 907   tree arg = PHI_ARG_DEF (phi, i);
 908
 909   fprintf (stderr, " Corrupt SSA across abnormal edge BB%d->BB%d\n",
 910            e->src->index, e->dest->index);
 911   fprintf (stderr, "Argument %d (", i);
 912   print_generic_expr (stderr, arg, TDF_SLIM);
 913   if (TREE_CODE (arg) != SSA_NAME)
 914     fprintf (stderr, ") is not an SSA_NAME.\n");
 915   else
 916     {
 917       gcc_assert (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg));
 918       fprintf (stderr, ") does not have the same base variable as the result ");
 919       print_generic_stmt (stderr, res, TDF_SLIM);
 920     }
 921
 922   internal_error ("SSA corruption");
 923 }
 924
 925
 926 /* Print a failure to coalesce a MUST_COALESCE pair X and Y.  */
 927
 928 static inline void
 929 fail_abnormal_edge_coalesce (int x, int y)
 930 {
 931   fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y);
 932   fprintf (stderr, " which are marked as MUST COALESCE.\n");
 933   print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
 934   fprintf (stderr, " and  ");
 935   print_generic_stmt (stderr, ssa_name (y), TDF_SLIM);
 936
 937   internal_error ("SSA corruption");
 938 }
 939
 940
 941 /* This function creates a var_map for the current function as well as creating
 942    a coalesce list for use later in the out of ssa process.  */
 943
 944 static var_map
 945 create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 946 {
 947   block_stmt_iterator bsi;
 948   basic_block bb;
 949   tree var;
 950   tree stmt;
 951   tree first;
 952   var_map map;
 953   ssa_op_iter iter;
 954   int v1, v2, cost;
 955   unsigned i;
 956
 957 #ifdef ENABLE_CHECKING
 958   bitmap used_in_real_ops;
 959   bitmap used_in_virtual_ops;
 960
 961   used_in_real_ops = BITMAP_ALLOC (NULL);
 962   used_in_virtual_ops = BITMAP_ALLOC (NULL);
 963 #endif
 964
 965   map = init_var_map (num_ssa_names + 1);
 966
 967   FOR_EACH_BB (bb)
 968     {
 969       tree phi, arg;
 970
 971       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 972         {
 973           int i;
 974           int ver;
 975           tree res;
 976           bool saw_copy = false;
 977
 978           res = PHI_RESULT (phi);
 979           ver = SSA_NAME_VERSION (res);
 980           register_ssa_partition (map, res);
 981
 982           /* Register ssa_names and coalesces between the args and the result
 983              of all PHI.  */
 984           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 985             {
 986               edge e = PHI_ARG_EDGE (phi, i);
 987               arg = PHI_ARG_DEF (phi, i);
 988               if (TREE_CODE (arg) == SSA_NAME)
 989                 register_ssa_partition (map, arg);
 990               if (TREE_CODE (arg) == SSA_NAME
 991                   && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
 992                 {
 993                   saw_copy = true;
 994                   bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
 995                   if ((e->flags & EDGE_ABNORMAL) == 0)
 996                     {
 997                       int cost = coalesce_cost_edge (e);
 998                       if (cost == 1 && has_single_use (arg))
 999                         add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg));
1000                       else
1001                         add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost);
1002                     }
1003                 }
1004               else
1005                 if (e->flags & EDGE_ABNORMAL)
1006                   abnormal_corrupt (phi, i);
1007             }
1008           if (saw_copy)
1009             bitmap_set_bit (used_in_copy, ver);
1010         }
1011
1012       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1013         {
1014           stmt = bsi_stmt (bsi);
1015
1016           /* Register USE and DEF operands in each statement.  */
1017           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1018             register_ssa_partition (map, var);
1019
1020           /* Check for copy coalesces.  */
1021           switch (TREE_CODE (stmt))
1022             {
1023             case GIMPLE_MODIFY_STMT:
1024               {
1025                 tree op1 = GIMPLE_STMT_OPERAND (stmt, 0);
1026                 tree op2 = GIMPLE_STMT_OPERAND (stmt, 1);
1027                 if (TREE_CODE (op1) == SSA_NAME
1028                     && TREE_CODE (op2) == SSA_NAME
1029                     && SSA_NAME_VAR (op1) == SSA_NAME_VAR (op2))
1030                   {
1031                     v1 = SSA_NAME_VERSION (op1);
1032                     v2 = SSA_NAME_VERSION (op2);
1033                     cost = coalesce_cost_bb (bb);
1034                     add_coalesce (cl, v1, v2, cost);
1035                     bitmap_set_bit (used_in_copy, v1);
1036                     bitmap_set_bit (used_in_copy, v2);
1037                   }
1038               }
1039               break;
1040
1041             case ASM_EXPR:
1042               {
1043                 unsigned long noutputs, i;
1044                 tree *outputs, link;
1045                 noutputs = list_length (ASM_OUTPUTS (stmt));
1046                 outputs = (tree *) alloca (noutputs * sizeof (tree));
1047                 for (i = 0, link = ASM_OUTPUTS (stmt); link;
1048                      ++i, link = TREE_CHAIN (link))
1049                   outputs[i] = TREE_VALUE (link);
1050
1051                 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
1052                   {
1053                     const char *constraint
1054                       = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1055                     tree input = TREE_VALUE (link);
1056                     char *end;
1057                     unsigned long match;
1058
1059                     if (TREE_CODE (input) != SSA_NAME)
1060                       continue;
1061
1062                     match = strtoul (constraint, &end, 10);
1063                     if (match >= noutputs || end == constraint)
1064                       continue;
1065
1066                     if (TREE_CODE (outputs[match]) != SSA_NAME)
1067                       continue;
1068
1069                     v1 = SSA_NAME_VERSION (outputs[match]);
1070                     v2 = SSA_NAME_VERSION (input);
1071
1072                     if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
1073                       {
1074                         cost = coalesce_cost (REG_BR_PROB_BASE,
1075                                               maybe_hot_bb_p (bb),
1076                                               false);
1077                         add_coalesce (cl, v1, v2, cost);
1078                         bitmap_set_bit (used_in_copy, v1);
1079                         bitmap_set_bit (used_in_copy, v2);
1080                       }
1081                   }
1082                 break;
1083               }
1084
1085             default:
1086               break;
1087             }
1088
1089 #ifdef ENABLE_CHECKING
1090           /* Mark real uses and defs.  */
1091           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
1092             bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
1093
1094           /* Validate that virtual ops don't get used in funny ways.  */
1095           FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
1096             {
1097               bitmap_set_bit (used_in_virtual_ops,
1098                               DECL_UID (SSA_NAME_VAR (var)));
1099             }
1100
1101 #endif /* ENABLE_CHECKING */
1102         }
1103     }
1104
1105   /* Now process result decls and live on entry variables for entry into
1106      the coalesce list.  */
1107   first = NULL_TREE;
1108   for (i = 1; i < num_ssa_names; i++)
1109     {
1110       var = map->partition_to_var[i];
1111       if (var != NULL_TREE)
1112         {
1113           /* Add coalesces between all the result decls.  */
1114           if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
1115             {
1116               if (first == NULL_TREE)
1117                 first = var;
1118               else
1119                 {
1120                   gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first));
1121                   v1 = SSA_NAME_VERSION (first);
1122                   v2 = SSA_NAME_VERSION (var);
1123                   bitmap_set_bit (used_in_copy, v1);
1124                   bitmap_set_bit (used_in_copy, v2);
1125                   cost = coalesce_cost_bb (EXIT_BLOCK_PTR);
1126                   add_coalesce (cl, v1, v2, cost);
1127                 }
1128             }
1129           /* Mark any default_def variables as being in the coalesce list
1130              since they will have to be coalesced with the base variable.  If
1131              not marked as present, they won't be in the coalesce view. */
1132           if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
1133             bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
1134         }
1135     }
1136
1137 #if defined ENABLE_CHECKING
1138   {
1139     unsigned i;
1140     bitmap both = BITMAP_ALLOC (NULL);
1141     bitmap_and (both, used_in_real_ops, used_in_virtual_ops);
1142     if (!bitmap_empty_p (both))
1143       {
1144         bitmap_iterator bi;
1145
1146         EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi)
1147           fprintf (stderr, "Variable %s used in real and virtual operands\n",
1148                    get_name (referenced_var (i)));
1149         internal_error ("SSA corruption");
1150       }
1151
1152     BITMAP_FREE (used_in_real_ops);
1153     BITMAP_FREE (used_in_virtual_ops);
1154     BITMAP_FREE (both);
1155   }
1156 #endif
1157
1158   return map;
1159 }
1160
1161
1162 /* Attempt to coalesce ssa versions X and Y together using the partition
1163    mapping in MAP and checking conflicts in GRAPH.  Output any debug info to
1164    DEBUG, if it is nun-NULL.  */
1165
1166 static inline bool
1167 attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
1168                   FILE *debug)
1169 {
1170   int z;
1171   tree var1, var2;
1172   int p1, p2;
1173
1174   p1 = var_to_partition (map, ssa_name (x));
1175   p2 = var_to_partition (map, ssa_name (y));
1176
1177   if (debug)
1178     {
1179       fprintf (debug, "(%d)", x);
1180       print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
1181       fprintf (debug, " & (%d)", y);
1182       print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
1183     }
1184
1185   if (p1 == p2)
1186     {
1187       if (debug)
1188         fprintf (debug, ": Already Coalesced.\n");
1189       return true;
1190     }
1191
1192   if (debug)
1193     fprintf (debug, " [map: %d, %d] ", p1, p2);
1194
1195
1196   if (!ssa_conflicts_test_p (graph, p1, p2))
1197     {
1198       var1 = partition_to_var (map, p1);
1199       var2 = partition_to_var (map, p2);
1200       z = var_union (map, var1, var2);
1201       if (z == NO_PARTITION)
1202         {
1203           if (debug)
1204             fprintf (debug, ": Unable to perform partition union.\n");
1205           return false;
1206         }
1207
1208       /* z is the new combined partition.  Remove the other partition from
1209          the list, and merge the conflicts.  */
1210       if (z == p1)
1211         ssa_conflicts_merge (graph, p1, p2);
1212       else
1213         ssa_conflicts_merge (graph, p2, p1);
1214
1215       if (debug)
1216         fprintf (debug, ": Success -> %d\n", z);
1217       return true;
1218     }
1219
1220   if (debug)
1221     fprintf (debug, ": Fail due to conflict\n");
1222
1223   return false;
1224 }
1225
1226
1227 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
1228    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
1229
1230 static void
1231 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
1232                      FILE *debug)
1233 {
1234   int x = 0, y = 0;
1235   tree var1, var2, phi;
1236   int cost;
1237   basic_block bb;
1238   edge e;
1239   edge_iterator ei;
1240
1241   /* First, coalesce all the copies across abnormal edges.  These are not placed
1242      in the coalesce list because they do not need to be sorted, and simply
1243      consume extra memory/compilation time in large programs.  */
1244
1245   FOR_EACH_BB (bb)
1246     {
1247       FOR_EACH_EDGE (e, ei, bb->preds)
1248         if (e->flags & EDGE_ABNORMAL)
1249           {
1250             for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1251               {
1252                 tree res = PHI_RESULT (phi);
1253                 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
1254                 int v1 = SSA_NAME_VERSION (res);
1255                 int v2 = SSA_NAME_VERSION (arg);
1256
1257                 if (SSA_NAME_VAR (arg) != SSA_NAME_VAR (res))
1258                   abnormal_corrupt (phi, e->dest_idx);
1259
1260                 if (debug)
1261                   fprintf (debug, "Abnormal coalesce: ");
1262
1263                 if (!attempt_coalesce (map, graph, v1, v2, debug))
1264                   fail_abnormal_edge_coalesce (v1, v2);
1265               }
1266           }
1267     }
1268
1269   /* Now process the items in the coalesce list.  */
1270
1271   while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE)
1272     {
1273       var1 = ssa_name (x);
1274       var2 = ssa_name (y);
1275
1276       /* Assert the coalesces have the same base variable.  */
1277       gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2));
1278
1279       if (debug)
1280         fprintf (debug, "Coalesce list: ");
1281       attempt_coalesce (map, graph, x, y, debug);
1282     }
1283 }
1284
1285
1286 /* Reduce the number of copies by coalescing variables in the function.  Return
1287    a partition map with the resulting coalesces.  */
1288
1289 extern var_map
1290 coalesce_ssa_name (void)
1291 {
1292   unsigned num, x;
1293   tree_live_info_p liveinfo;
1294   ssa_conflicts_p graph;
1295   coalesce_list_p cl;
1296   bitmap used_in_copies = BITMAP_ALLOC (NULL);
1297   var_map map;
1298
1299   cl = create_coalesce_list ();
1300   map = create_outofssa_var_map (cl, used_in_copies);
1301
1302   /* Don't calculate live ranges for variables not in the coalesce list.  */
1303   partition_view_bitmap (map, used_in_copies, true);
1304   BITMAP_FREE (used_in_copies);
1305
1306   if (num_var_partitions (map) < 1)
1307     {
1308       delete_coalesce_list (cl);
1309       return map;
1310     }
1311
1312   if (dump_file && (dump_flags & TDF_DETAILS))
1313     dump_var_map (dump_file, map);
1314
1315   liveinfo = calculate_live_ranges (map);
1316
1317   if (dump_file && (dump_flags & TDF_DETAILS))
1318     dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
1319
1320   /* Build a conflict graph.  */
1321   graph = build_ssa_conflict_graph (liveinfo);
1322   delete_tree_live_info (liveinfo);
1323   if (dump_file && (dump_flags & TDF_DETAILS))
1324     ssa_conflicts_dump (dump_file, graph);
1325
1326   sort_coalesce_list (cl);
1327
1328   if (dump_file && (dump_flags & TDF_DETAILS))
1329     {
1330       fprintf (dump_file, "\nAfter sorting:\n");
1331       dump_coalesce_list (dump_file, cl);
1332     }
1333
1334   /* First, coalesce all live on entry variables to their base variable.
1335      This will ensure the first use is coming from the correct location.  */
1336
1337   num = num_var_partitions (map);
1338   for (x = 0 ; x < num; x++)
1339     {
1340       tree var = partition_to_var (map, x);
1341       tree root;
1342
1343       if (TREE_CODE (var) != SSA_NAME)
1344         continue;
1345
1346       root = SSA_NAME_VAR (var);
1347       if (gimple_default_def (cfun, root) == var)
1348         {
1349           /* This root variable should have not already been assigned
1350              to another partition which is not coalesced with this one.  */
1351           gcc_assert (!var_ann (root)->out_of_ssa_tag);
1352
1353           if (dump_file && (dump_flags & TDF_DETAILS))
1354             {
1355               print_exprs (dump_file, "Must coalesce ", var,
1356                            " with the root variable ", root, ".\n");
1357             }
1358           change_partition_var (map, root, x);
1359         }
1360     }
1361
1362   if (dump_file && (dump_flags & TDF_DETAILS))
1363     dump_var_map (dump_file, map);
1364
1365   /* Now coalesce everything in the list.  */
1366   coalesce_partitions (map, graph, cl,
1367                        ((dump_flags & TDF_DETAILS) ? dump_file
1368                                                    : NULL));
1369
1370   delete_coalesce_list (cl);
1371   ssa_conflicts_delete (graph);
1372
1373   return map;
1374 }
1375