gcc/tree-ssa-coalesce.c

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