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