1 /* Coalesce SSA_NAMES together for the out-of-ssa pass. 2 Copyright (C) 2004-2018 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 "backend.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "predict.h" 28 #include "memmodel.h" 29 #include "tm_p.h" 30 #include "ssa.h" 31 #include "tree-ssa.h" 32 #include "tree-pretty-print.h" 33 #include "diagnostic-core.h" 34 #include "dumpfile.h" 35 #include "gimple-iterator.h" 36 #include "tree-ssa-live.h" 37 #include "tree-ssa-coalesce.h" 38 #include "explow.h" 39 #include "tree-dfa.h" 40 #include "stor-layout.h" 41 42 /* This set of routines implements a coalesce_list. This is an object which 43 is used to track pairs of ssa_names which are desirable to coalesce 44 together to avoid copies. Costs are associated with each pair, and when 45 all desired information has been collected, the object can be used to 46 order the pairs for processing. */ 47 48 /* This structure defines a pair entry. */ 49 50 struct coalesce_pair 51 { 52 int first_element; 53 int second_element; 54 int cost; 55 56 /* A count of the number of unique partitions this pair would conflict 57 with if coalescing was successful. This is the secondary sort key, 58 given two pairs with equal costs, we will prefer the pair with a smaller 59 conflict set. 60 61 This is lazily initialized when we discover two coalescing pairs have 62 the same primary cost. 63 64 Note this is not updated and propagated as pairs are coalesced. */ 65 int conflict_count; 66 67 /* The order in which coalescing pairs are discovered is recorded in this 68 field, which is used as the final tie breaker when sorting coalesce 69 pairs. */ 70 int index; 71 }; 72 73 /* This represents a conflict graph. Implemented as an array of bitmaps. 74 A full matrix is used for conflicts rather than just upper triangular form. 75 this makes it much simpler and faster to perform conflict merges. */ 76 77 struct ssa_conflicts 78 { 79 bitmap_obstack obstack; /* A place to allocate our bitmaps. */ 80 vec<bitmap> conflicts; 81 }; 82 83 /* The narrow API of the qsort comparison function doesn't allow easy 84 access to additional arguments. So we have two globals (ick) to hold 85 the data we need. They're initialized before the call to qsort and 86 wiped immediately after. */ 87 static ssa_conflicts *conflicts_; 88 static var_map map_; 89 90 /* Coalesce pair hashtable helpers. */ 91 92 struct coalesce_pair_hasher : nofree_ptr_hash <coalesce_pair> 93 { 94 static inline hashval_t hash (const coalesce_pair *); 95 static inline bool equal (const coalesce_pair *, const coalesce_pair *); 96 }; 97 98 /* Hash function for coalesce list. Calculate hash for PAIR. */ 99 100 inline hashval_t 101 coalesce_pair_hasher::hash (const coalesce_pair *pair) 102 { 103 hashval_t a = (hashval_t)(pair->first_element); 104 hashval_t b = (hashval_t)(pair->second_element); 105 106 return b * (b - 1) / 2 + a; 107 } 108 109 /* Equality function for coalesce list hash table. Compare PAIR1 and PAIR2, 110 returning TRUE if the two pairs are equivalent. */ 111 112 inline bool 113 coalesce_pair_hasher::equal (const coalesce_pair *p1, const coalesce_pair *p2) 114 { 115 return (p1->first_element == p2->first_element 116 && p1->second_element == p2->second_element); 117 } 118 119 typedef hash_table<coalesce_pair_hasher> coalesce_table_type; 120 typedef coalesce_table_type::iterator coalesce_iterator_type; 121 122 123 struct cost_one_pair 124 { 125 int first_element; 126 int second_element; 127 cost_one_pair *next; 128 }; 129 130 /* This structure maintains the list of coalesce pairs. */ 131 132 struct coalesce_list 133 { 134 coalesce_table_type *list; /* Hash table. */ 135 coalesce_pair **sorted; /* List when sorted. */ 136 int num_sorted; /* Number in the sorted list. */ 137 cost_one_pair *cost_one_list;/* Single use coalesces with cost 1. */ 138 }; 139 140 #define NO_BEST_COALESCE -1 141 #define MUST_COALESCE_COST INT_MAX 142 143 144 /* Return cost of execution of copy instruction with FREQUENCY. */ 145 146 static inline int 147 coalesce_cost (int frequency, bool optimize_for_size) 148 { 149 /* Base costs on BB frequencies bounded by 1. */ 150 int cost = frequency; 151 152 if (!cost) 153 cost = 1; 154 155 if (optimize_for_size) 156 cost = 1; 157 158 return cost; 159 } 160 161 162 /* Return the cost of executing a copy instruction in basic block BB. */ 163 164 static inline int 165 coalesce_cost_bb (basic_block bb) 166 { 167 return coalesce_cost (bb->count.to_frequency (cfun), 168 optimize_bb_for_size_p (bb)); 169 } 170 171 172 /* Return the cost of executing a copy instruction on edge E. */ 173 174 static inline int 175 coalesce_cost_edge (edge e) 176 { 177 int mult = 1; 178 179 /* Inserting copy on critical edge costs more than inserting it elsewhere. */ 180 if (EDGE_CRITICAL_P (e)) 181 mult = 2; 182 if (e->flags & EDGE_ABNORMAL) 183 return MUST_COALESCE_COST; 184 if (e->flags & EDGE_EH) 185 { 186 edge e2; 187 edge_iterator ei; 188 FOR_EACH_EDGE (e2, ei, e->dest->preds) 189 if (e2 != e) 190 { 191 /* Putting code on EH edge that leads to BB 192 with multiple predecestors imply splitting of 193 edge too. */ 194 if (mult < 2) 195 mult = 2; 196 /* If there are multiple EH predecestors, we 197 also copy EH regions and produce separate 198 landing pad. This is expensive. */ 199 if (e2->flags & EDGE_EH) 200 { 201 mult = 5; 202 break; 203 } 204 } 205 } 206 207 return coalesce_cost (EDGE_FREQUENCY (e), 208 optimize_edge_for_size_p (e)) * mult; 209 } 210 211 212 /* Retrieve a pair to coalesce from the cost_one_list in CL. Returns the 213 2 elements via P1 and P2. 1 is returned by the function if there is a pair, 214 NO_BEST_COALESCE is returned if there aren't any. */ 215 216 static inline int 217 pop_cost_one_pair (coalesce_list *cl, int *p1, int *p2) 218 { 219 cost_one_pair *ptr; 220 221 ptr = cl->cost_one_list; 222 if (!ptr) 223 return NO_BEST_COALESCE; 224 225 *p1 = ptr->first_element; 226 *p2 = ptr->second_element; 227 cl->cost_one_list = ptr->next; 228 229 free (ptr); 230 231 return 1; 232 } 233 234 /* Retrieve the most expensive remaining pair to coalesce from CL. Returns the 235 2 elements via P1 and P2. Their calculated cost is returned by the function. 236 NO_BEST_COALESCE is returned if the coalesce list is empty. */ 237 238 static inline int 239 pop_best_coalesce (coalesce_list *cl, int *p1, int *p2) 240 { 241 coalesce_pair *node; 242 int ret; 243 244 if (cl->sorted == NULL) 245 return pop_cost_one_pair (cl, p1, p2); 246 247 if (cl->num_sorted == 0) 248 return pop_cost_one_pair (cl, p1, p2); 249 250 node = cl->sorted[--(cl->num_sorted)]; 251 *p1 = node->first_element; 252 *p2 = node->second_element; 253 ret = node->cost; 254 free (node); 255 256 return ret; 257 } 258 259 260 /* Create a new empty coalesce list object and return it. */ 261 262 static inline coalesce_list * 263 create_coalesce_list (void) 264 { 265 coalesce_list *list; 266 unsigned size = num_ssa_names * 3; 267 268 if (size < 40) 269 size = 40; 270 271 list = (coalesce_list *) xmalloc (sizeof (struct coalesce_list)); 272 list->list = new coalesce_table_type (size); 273 list->sorted = NULL; 274 list->num_sorted = 0; 275 list->cost_one_list = NULL; 276 return list; 277 } 278 279 280 /* Delete coalesce list CL. */ 281 282 static inline void 283 delete_coalesce_list (coalesce_list *cl) 284 { 285 gcc_assert (cl->cost_one_list == NULL); 286 delete cl->list; 287 cl->list = NULL; 288 free (cl->sorted); 289 gcc_assert (cl->num_sorted == 0); 290 free (cl); 291 } 292 293 /* Return the number of unique coalesce pairs in CL. */ 294 295 static inline int 296 num_coalesce_pairs (coalesce_list *cl) 297 { 298 return cl->list->elements (); 299 } 300 301 /* Find a matching coalesce pair object in CL for the pair P1 and P2. If 302 one isn't found, return NULL if CREATE is false, otherwise create a new 303 coalesce pair object and return it. */ 304 305 static coalesce_pair * 306 find_coalesce_pair (coalesce_list *cl, int p1, int p2, bool create) 307 { 308 struct coalesce_pair p; 309 coalesce_pair **slot; 310 unsigned int hash; 311 312 /* Normalize so that p1 is the smaller value. */ 313 if (p2 < p1) 314 { 315 p.first_element = p2; 316 p.second_element = p1; 317 } 318 else 319 { 320 p.first_element = p1; 321 p.second_element = p2; 322 } 323 324 hash = coalesce_pair_hasher::hash (&p); 325 slot = cl->list->find_slot_with_hash (&p, hash, create ? INSERT : NO_INSERT); 326 if (!slot) 327 return NULL; 328 329 if (!*slot) 330 { 331 struct coalesce_pair * pair = XNEW (struct coalesce_pair); 332 gcc_assert (cl->sorted == NULL); 333 pair->first_element = p.first_element; 334 pair->second_element = p.second_element; 335 pair->cost = 0; 336 pair->index = num_coalesce_pairs (cl); 337 pair->conflict_count = 0; 338 *slot = pair; 339 } 340 341 return (struct coalesce_pair *) *slot; 342 } 343 344 static inline void 345 add_cost_one_coalesce (coalesce_list *cl, int p1, int p2) 346 { 347 cost_one_pair *pair; 348 349 pair = XNEW (cost_one_pair); 350 pair->first_element = p1; 351 pair->second_element = p2; 352 pair->next = cl->cost_one_list; 353 cl->cost_one_list = pair; 354 } 355 356 357 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE. */ 358 359 static inline void 360 add_coalesce (coalesce_list *cl, int p1, int p2, int value) 361 { 362 coalesce_pair *node; 363 364 gcc_assert (cl->sorted == NULL); 365 if (p1 == p2) 366 return; 367 368 node = find_coalesce_pair (cl, p1, p2, true); 369 370 /* Once the value is at least MUST_COALESCE_COST - 1, leave it that way. */ 371 if (node->cost < MUST_COALESCE_COST - 1) 372 { 373 if (value < MUST_COALESCE_COST - 1) 374 node->cost += value; 375 else 376 node->cost = value; 377 } 378 } 379 380 /* Compute and record how many unique conflicts would exist for the 381 representative partition for each coalesce pair in CL. 382 383 CONFLICTS is the conflict graph and MAP is the current partition view. */ 384 385 static void 386 initialize_conflict_count (coalesce_pair *p, 387 ssa_conflicts *conflicts, 388 var_map map) 389 { 390 int p1 = var_to_partition (map, ssa_name (p->first_element)); 391 int p2 = var_to_partition (map, ssa_name (p->second_element)); 392 393 /* 4 cases. If both P1 and P2 have conflicts, then build their 394 union and count the members. Else handle the degenerate cases 395 in the obvious ways. */ 396 if (conflicts->conflicts[p1] && conflicts->conflicts[p2]) 397 p->conflict_count = bitmap_count_unique_bits (conflicts->conflicts[p1], 398 conflicts->conflicts[p2]); 399 else if (conflicts->conflicts[p1]) 400 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p1]); 401 else if (conflicts->conflicts[p2]) 402 p->conflict_count = bitmap_count_bits (conflicts->conflicts[p2]); 403 else 404 p->conflict_count = 0; 405 } 406 407 408 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order. */ 409 410 static int 411 compare_pairs (const void *p1, const void *p2) 412 { 413 coalesce_pair *const *const pp1 = (coalesce_pair *const *) p1; 414 coalesce_pair *const *const pp2 = (coalesce_pair *const *) p2; 415 int result; 416 417 result = (* pp1)->cost - (* pp2)->cost; 418 /* We use the size of the resulting conflict set as the secondary sort key. 419 Given two equal costing coalesce pairs, we want to prefer the pair that 420 has the smaller conflict set. */ 421 if (result == 0) 422 { 423 if (flag_expensive_optimizations) 424 { 425 /* Lazily initialize the conflict counts as it's fairly expensive 426 to compute. */ 427 if ((*pp2)->conflict_count == 0) 428 initialize_conflict_count (*pp2, conflicts_, map_); 429 if ((*pp1)->conflict_count == 0) 430 initialize_conflict_count (*pp1, conflicts_, map_); 431 432 result = (*pp2)->conflict_count - (*pp1)->conflict_count; 433 } 434 435 /* And if everything else is equal, then sort based on which 436 coalesce pair was found first. */ 437 if (result == 0) 438 result = (*pp2)->index - (*pp1)->index; 439 } 440 441 return result; 442 } 443 444 /* Iterate over CL using ITER, returning values in PAIR. */ 445 446 #define FOR_EACH_PARTITION_PAIR(PAIR, ITER, CL) \ 447 FOR_EACH_HASH_TABLE_ELEMENT (*(CL)->list, (PAIR), coalesce_pair_p, (ITER)) 448 449 450 /* Prepare CL for removal of preferred pairs. When finished they are sorted 451 in order from most important coalesce to least important. */ 452 453 static void 454 sort_coalesce_list (coalesce_list *cl, ssa_conflicts *conflicts, var_map map) 455 { 456 unsigned x, num; 457 coalesce_pair *p; 458 coalesce_iterator_type ppi; 459 460 gcc_assert (cl->sorted == NULL); 461 462 num = num_coalesce_pairs (cl); 463 cl->num_sorted = num; 464 if (num == 0) 465 return; 466 467 /* Allocate a vector for the pair pointers. */ 468 cl->sorted = XNEWVEC (coalesce_pair *, num); 469 470 /* Populate the vector with pointers to the pairs. */ 471 x = 0; 472 FOR_EACH_PARTITION_PAIR (p, ppi, cl) 473 cl->sorted[x++] = p; 474 gcc_assert (x == num); 475 476 /* Already sorted. */ 477 if (num == 1) 478 return; 479 480 /* We don't want to depend on qsort_r, so we have to stuff away 481 additional data into globals so it can be referenced in 482 compare_pairs. */ 483 conflicts_ = conflicts; 484 map_ = map; 485 qsort (cl->sorted, num, sizeof (coalesce_pair *), compare_pairs); 486 conflicts_ = NULL; 487 map_ = NULL; 488 } 489 490 491 /* Send debug info for coalesce list CL to file F. */ 492 493 static void 494 dump_coalesce_list (FILE *f, coalesce_list *cl) 495 { 496 coalesce_pair *node; 497 coalesce_iterator_type ppi; 498 499 int x; 500 tree var; 501 502 if (cl->sorted == NULL) 503 { 504 fprintf (f, "Coalesce List:\n"); 505 FOR_EACH_PARTITION_PAIR (node, ppi, cl) 506 { 507 tree var1 = ssa_name (node->first_element); 508 tree var2 = ssa_name (node->second_element); 509 print_generic_expr (f, var1, TDF_SLIM); 510 fprintf (f, " <-> "); 511 print_generic_expr (f, var2, TDF_SLIM); 512 fprintf (f, " (%1d, %1d), ", node->cost, node->conflict_count); 513 fprintf (f, "\n"); 514 } 515 } 516 else 517 { 518 fprintf (f, "Sorted Coalesce list:\n"); 519 for (x = cl->num_sorted - 1 ; x >=0; x--) 520 { 521 node = cl->sorted[x]; 522 fprintf (f, "(%d, %d) ", node->cost, node->conflict_count); 523 var = ssa_name (node->first_element); 524 print_generic_expr (f, var, TDF_SLIM); 525 fprintf (f, " <-> "); 526 var = ssa_name (node->second_element); 527 print_generic_expr (f, var, TDF_SLIM); 528 fprintf (f, "\n"); 529 } 530 } 531 } 532 533 534 /* Return an empty new conflict graph for SIZE elements. */ 535 536 static inline ssa_conflicts * 537 ssa_conflicts_new (unsigned size) 538 { 539 ssa_conflicts *ptr; 540 541 ptr = XNEW (ssa_conflicts); 542 bitmap_obstack_initialize (&ptr->obstack); 543 ptr->conflicts.create (size); 544 ptr->conflicts.safe_grow_cleared (size); 545 return ptr; 546 } 547 548 549 /* Free storage for conflict graph PTR. */ 550 551 static inline void 552 ssa_conflicts_delete (ssa_conflicts *ptr) 553 { 554 bitmap_obstack_release (&ptr->obstack); 555 ptr->conflicts.release (); 556 free (ptr); 557 } 558 559 560 /* Test if elements X and Y conflict in graph PTR. */ 561 562 static inline bool 563 ssa_conflicts_test_p (ssa_conflicts *ptr, unsigned x, unsigned y) 564 { 565 bitmap bx = ptr->conflicts[x]; 566 bitmap by = ptr->conflicts[y]; 567 568 gcc_checking_assert (x != y); 569 570 if (bx) 571 /* Avoid the lookup if Y has no conflicts. */ 572 return by ? bitmap_bit_p (bx, y) : false; 573 else 574 return false; 575 } 576 577 578 /* Add a conflict with Y to the bitmap for X in graph PTR. */ 579 580 static inline void 581 ssa_conflicts_add_one (ssa_conflicts *ptr, unsigned x, unsigned y) 582 { 583 bitmap bx = ptr->conflicts[x]; 584 /* If there are no conflicts yet, allocate the bitmap and set bit. */ 585 if (! bx) 586 bx = ptr->conflicts[x] = BITMAP_ALLOC (&ptr->obstack); 587 bitmap_set_bit (bx, y); 588 } 589 590 591 /* Add conflicts between X and Y in graph PTR. */ 592 593 static inline void 594 ssa_conflicts_add (ssa_conflicts *ptr, unsigned x, unsigned y) 595 { 596 gcc_checking_assert (x != y); 597 ssa_conflicts_add_one (ptr, x, y); 598 ssa_conflicts_add_one (ptr, y, x); 599 } 600 601 602 /* Merge all Y's conflict into X in graph PTR. */ 603 604 static inline void 605 ssa_conflicts_merge (ssa_conflicts *ptr, unsigned x, unsigned y) 606 { 607 unsigned z; 608 bitmap_iterator bi; 609 bitmap bx = ptr->conflicts[x]; 610 bitmap by = ptr->conflicts[y]; 611 612 gcc_checking_assert (x != y); 613 if (! by) 614 return; 615 616 /* Add a conflict between X and every one Y has. If the bitmap doesn't 617 exist, then it has already been coalesced, and we don't need to add a 618 conflict. */ 619 EXECUTE_IF_SET_IN_BITMAP (by, 0, z, bi) 620 { 621 bitmap bz = ptr->conflicts[z]; 622 if (bz) 623 bitmap_set_bit (bz, x); 624 } 625 626 if (bx) 627 { 628 /* If X has conflicts, add Y's to X. */ 629 bitmap_ior_into (bx, by); 630 BITMAP_FREE (by); 631 ptr->conflicts[y] = NULL; 632 } 633 else 634 { 635 /* If X has no conflicts, simply use Y's. */ 636 ptr->conflicts[x] = by; 637 ptr->conflicts[y] = NULL; 638 } 639 } 640 641 642 /* Dump a conflicts graph. */ 643 644 static void 645 ssa_conflicts_dump (FILE *file, ssa_conflicts *ptr) 646 { 647 unsigned x; 648 bitmap b; 649 650 fprintf (file, "\nConflict graph:\n"); 651 652 FOR_EACH_VEC_ELT (ptr->conflicts, x, b) 653 if (b) 654 { 655 fprintf (file, "%d: ", x); 656 dump_bitmap (file, b); 657 } 658 } 659 660 661 /* This structure is used to efficiently record the current status of live 662 SSA_NAMES when building a conflict graph. 663 LIVE_BASE_VAR has a bit set for each base variable which has at least one 664 ssa version live. 665 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an 666 index, and is used to track what partitions of each base variable are 667 live. This makes it easy to add conflicts between just live partitions 668 with the same base variable. 669 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is 670 marked as being live. This delays clearing of these bitmaps until 671 they are actually needed again. */ 672 673 struct live_track 674 { 675 bitmap_obstack obstack; /* A place to allocate our bitmaps. */ 676 bitmap live_base_var; /* Indicates if a basevar is live. */ 677 bitmap *live_base_partitions; /* Live partitions for each basevar. */ 678 var_map map; /* Var_map being used for partition mapping. */ 679 }; 680 681 682 /* This routine will create a new live track structure based on the partitions 683 in MAP. */ 684 685 static live_track * 686 new_live_track (var_map map) 687 { 688 live_track *ptr; 689 int lim, x; 690 691 /* Make sure there is a partition view in place. */ 692 gcc_assert (map->partition_to_base_index != NULL); 693 694 ptr = (live_track *) xmalloc (sizeof (live_track)); 695 ptr->map = map; 696 lim = num_basevars (map); 697 bitmap_obstack_initialize (&ptr->obstack); 698 ptr->live_base_partitions = (bitmap *) xmalloc (sizeof (bitmap *) * lim); 699 ptr->live_base_var = BITMAP_ALLOC (&ptr->obstack); 700 for (x = 0; x < lim; x++) 701 ptr->live_base_partitions[x] = BITMAP_ALLOC (&ptr->obstack); 702 return ptr; 703 } 704 705 706 /* This routine will free the memory associated with PTR. */ 707 708 static void 709 delete_live_track (live_track *ptr) 710 { 711 bitmap_obstack_release (&ptr->obstack); 712 free (ptr->live_base_partitions); 713 free (ptr); 714 } 715 716 717 /* This function will remove PARTITION from the live list in PTR. */ 718 719 static inline void 720 live_track_remove_partition (live_track *ptr, int partition) 721 { 722 int root; 723 724 root = basevar_index (ptr->map, partition); 725 bitmap_clear_bit (ptr->live_base_partitions[root], partition); 726 /* If the element list is empty, make the base variable not live either. */ 727 if (bitmap_empty_p (ptr->live_base_partitions[root])) 728 bitmap_clear_bit (ptr->live_base_var, root); 729 } 730 731 732 /* This function will adds PARTITION to the live list in PTR. */ 733 734 static inline void 735 live_track_add_partition (live_track *ptr, int partition) 736 { 737 int root; 738 739 root = basevar_index (ptr->map, partition); 740 /* If this base var wasn't live before, it is now. Clear the element list 741 since it was delayed until needed. */ 742 if (bitmap_set_bit (ptr->live_base_var, root)) 743 bitmap_clear (ptr->live_base_partitions[root]); 744 bitmap_set_bit (ptr->live_base_partitions[root], partition); 745 746 } 747 748 749 /* Clear the live bit for VAR in PTR. */ 750 751 static inline void 752 live_track_clear_var (live_track *ptr, tree var) 753 { 754 int p; 755 756 p = var_to_partition (ptr->map, var); 757 if (p != NO_PARTITION) 758 live_track_remove_partition (ptr, p); 759 } 760 761 762 /* Return TRUE if VAR is live in PTR. */ 763 764 static inline bool 765 live_track_live_p (live_track *ptr, tree var) 766 { 767 int p, root; 768 769 p = var_to_partition (ptr->map, var); 770 if (p != NO_PARTITION) 771 { 772 root = basevar_index (ptr->map, p); 773 if (bitmap_bit_p (ptr->live_base_var, root)) 774 return bitmap_bit_p (ptr->live_base_partitions[root], p); 775 } 776 return false; 777 } 778 779 780 /* This routine will add USE to PTR. USE will be marked as live in both the 781 ssa live map and the live bitmap for the root of USE. */ 782 783 static inline void 784 live_track_process_use (live_track *ptr, tree use) 785 { 786 int p; 787 788 p = var_to_partition (ptr->map, use); 789 if (p == NO_PARTITION) 790 return; 791 792 /* Mark as live in the appropriate live list. */ 793 live_track_add_partition (ptr, p); 794 } 795 796 797 /* This routine will process a DEF in PTR. DEF will be removed from the live 798 lists, and if there are any other live partitions with the same base 799 variable, conflicts will be added to GRAPH. */ 800 801 static inline void 802 live_track_process_def (live_track *ptr, tree def, ssa_conflicts *graph) 803 { 804 int p, root; 805 bitmap b; 806 unsigned x; 807 bitmap_iterator bi; 808 809 p = var_to_partition (ptr->map, def); 810 if (p == NO_PARTITION) 811 return; 812 813 /* Clear the liveness bit. */ 814 live_track_remove_partition (ptr, p); 815 816 /* If the bitmap isn't empty now, conflicts need to be added. */ 817 root = basevar_index (ptr->map, p); 818 if (bitmap_bit_p (ptr->live_base_var, root)) 819 { 820 b = ptr->live_base_partitions[root]; 821 EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi) 822 ssa_conflicts_add (graph, p, x); 823 } 824 } 825 826 827 /* Initialize PTR with the partitions set in INIT. */ 828 829 static inline void 830 live_track_init (live_track *ptr, bitmap init) 831 { 832 unsigned p; 833 bitmap_iterator bi; 834 835 /* Mark all live on exit partitions. */ 836 EXECUTE_IF_SET_IN_BITMAP (init, 0, p, bi) 837 live_track_add_partition (ptr, p); 838 } 839 840 841 /* This routine will clear all live partitions in PTR. */ 842 843 static inline void 844 live_track_clear_base_vars (live_track *ptr) 845 { 846 /* Simply clear the live base list. Anything marked as live in the element 847 lists will be cleared later if/when the base variable ever comes alive 848 again. */ 849 bitmap_clear (ptr->live_base_var); 850 } 851 852 853 /* Build a conflict graph based on LIVEINFO. Any partitions which are in the 854 partition view of the var_map liveinfo is based on get entries in the 855 conflict graph. Only conflicts between ssa_name partitions with the same 856 base variable are added. */ 857 858 static ssa_conflicts * 859 build_ssa_conflict_graph (tree_live_info_p liveinfo) 860 { 861 ssa_conflicts *graph; 862 var_map map; 863 basic_block bb; 864 ssa_op_iter iter; 865 live_track *live; 866 basic_block entry; 867 868 /* If inter-variable coalescing is enabled, we may attempt to 869 coalesce variables from different base variables, including 870 different parameters, so we have to make sure default defs live 871 at the entry block conflict with each other. */ 872 if (flag_tree_coalesce_vars) 873 entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 874 else 875 entry = NULL; 876 877 map = live_var_map (liveinfo); 878 graph = ssa_conflicts_new (num_var_partitions (map)); 879 880 live = new_live_track (map); 881 882 FOR_EACH_BB_FN (bb, cfun) 883 { 884 /* Start with live on exit temporaries. */ 885 live_track_init (live, live_on_exit (liveinfo, bb)); 886 887 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); 888 gsi_prev (&gsi)) 889 { 890 tree var; 891 gimple *stmt = gsi_stmt (gsi); 892 893 /* A copy between 2 partitions does not introduce an interference 894 by itself. If they did, you would never be able to coalesce 895 two things which are copied. If the two variables really do 896 conflict, they will conflict elsewhere in the program. 897 898 This is handled by simply removing the SRC of the copy from the 899 live list, and processing the stmt normally. */ 900 if (is_gimple_assign (stmt)) 901 { 902 tree lhs = gimple_assign_lhs (stmt); 903 tree rhs1 = gimple_assign_rhs1 (stmt); 904 if (gimple_assign_copy_p (stmt) 905 && TREE_CODE (lhs) == SSA_NAME 906 && TREE_CODE (rhs1) == SSA_NAME) 907 live_track_clear_var (live, rhs1); 908 } 909 else if (is_gimple_debug (stmt)) 910 continue; 911 912 /* For stmts with more than one SSA_NAME definition pretend all the 913 SSA_NAME outputs but the first one are live at this point, so 914 that conflicts are added in between all those even when they are 915 actually not really live after the asm, because expansion might 916 copy those into pseudos after the asm and if multiple outputs 917 share the same partition, it might overwrite those that should 918 be live. E.g. 919 asm volatile (".." : "=r" (a) : "=r" (b) : "0" (a), "1" (a)); 920 return a; 921 See PR70593. */ 922 bool first = true; 923 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) 924 if (first) 925 first = false; 926 else 927 live_track_process_use (live, var); 928 929 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) 930 live_track_process_def (live, var, graph); 931 932 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 933 live_track_process_use (live, var); 934 } 935 936 /* If result of a PHI is unused, looping over the statements will not 937 record any conflicts since the def was never live. Since the PHI node 938 is going to be translated out of SSA form, it will insert a copy. 939 There must be a conflict recorded between the result of the PHI and 940 any variables that are live. Otherwise the out-of-ssa translation 941 may create incorrect code. */ 942 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 943 gsi_next (&gsi)) 944 { 945 gphi *phi = gsi.phi (); 946 tree result = PHI_RESULT (phi); 947 if (live_track_live_p (live, result)) 948 live_track_process_def (live, result, graph); 949 } 950 951 /* Pretend there are defs for params' default defs at the start 952 of the (post-)entry block. This will prevent PARM_DECLs from 953 coalescing into the same partition. Although RESULT_DECLs' 954 default defs don't have a useful initial value, we have to 955 prevent them from coalescing with PARM_DECLs' default defs 956 too, otherwise assign_parms would attempt to assign different 957 RTL to the same partition. */ 958 if (bb == entry) 959 { 960 unsigned i; 961 tree var; 962 963 FOR_EACH_SSA_NAME (i, var, cfun) 964 { 965 if (!SSA_NAME_IS_DEFAULT_DEF (var) 966 || !SSA_NAME_VAR (var) 967 || VAR_P (SSA_NAME_VAR (var))) 968 continue; 969 970 live_track_process_def (live, var, graph); 971 /* Process a use too, so that it remains live and 972 conflicts with other parms' default defs, even unused 973 ones. */ 974 live_track_process_use (live, var); 975 } 976 } 977 978 live_track_clear_base_vars (live); 979 } 980 981 delete_live_track (live); 982 return graph; 983 } 984 985 986 /* Shortcut routine to print messages to file F of the form: 987 "STR1 EXPR1 STR2 EXPR2 STR3." */ 988 989 static inline void 990 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2, 991 tree expr2, const char *str3) 992 { 993 fprintf (f, "%s", str1); 994 print_generic_expr (f, expr1, TDF_SLIM); 995 fprintf (f, "%s", str2); 996 print_generic_expr (f, expr2, TDF_SLIM); 997 fprintf (f, "%s", str3); 998 } 999 1000 1001 /* Print a failure to coalesce a MUST_COALESCE pair X and Y. */ 1002 1003 static inline void 1004 fail_abnormal_edge_coalesce (int x, int y) 1005 { 1006 fprintf (stderr, "\nUnable to coalesce ssa_names %d and %d",x, y); 1007 fprintf (stderr, " which are marked as MUST COALESCE.\n"); 1008 print_generic_expr (stderr, ssa_name (x), TDF_SLIM); 1009 fprintf (stderr, " and "); 1010 print_generic_stmt (stderr, ssa_name (y), TDF_SLIM); 1011 1012 internal_error ("SSA corruption"); 1013 } 1014 1015 /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which 1016 assign_parms may ask for a default partition. */ 1017 1018 static void 1019 for_all_parms (void (*callback)(tree var, void *arg), void *arg) 1020 { 1021 for (tree var = DECL_ARGUMENTS (current_function_decl); var; 1022 var = DECL_CHAIN (var)) 1023 callback (var, arg); 1024 if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) 1025 callback (DECL_RESULT (current_function_decl), arg); 1026 if (cfun->static_chain_decl) 1027 callback (cfun->static_chain_decl, arg); 1028 } 1029 1030 /* Create a default def for VAR. */ 1031 1032 static void 1033 create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) 1034 { 1035 if (!is_gimple_reg (var)) 1036 return; 1037 1038 tree ssa = get_or_create_ssa_default_def (cfun, var); 1039 gcc_assert (ssa); 1040 } 1041 1042 /* Register VAR's default def in MAP. */ 1043 1044 static void 1045 register_default_def (tree var, void *arg ATTRIBUTE_UNUSED) 1046 { 1047 if (!is_gimple_reg (var)) 1048 return; 1049 1050 tree ssa = ssa_default_def (cfun, var); 1051 gcc_assert (ssa); 1052 } 1053 1054 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL, 1055 and the DECL's default def is unused (i.e., it was introduced by 1056 create_default_def), mark VAR and the default def for 1057 coalescing. */ 1058 1059 static void 1060 coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy) 1061 { 1062 if (SSA_NAME_IS_DEFAULT_DEF (var) 1063 || !SSA_NAME_VAR (var) 1064 || VAR_P (SSA_NAME_VAR (var))) 1065 return; 1066 1067 tree ssa = ssa_default_def (cfun, SSA_NAME_VAR (var)); 1068 if (!has_zero_uses (ssa)) 1069 return; 1070 1071 add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var)); 1072 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); 1073 /* Default defs will have their used_in_copy bits set at the end of 1074 create_outofssa_var_map. */ 1075 } 1076 1077 /* This function creates a var_map for the current function as well as creating 1078 a coalesce list for use later in the out of ssa process. */ 1079 1080 static var_map 1081 create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) 1082 { 1083 gimple_stmt_iterator gsi; 1084 basic_block bb; 1085 tree var; 1086 gimple *stmt; 1087 tree first; 1088 var_map map; 1089 int v1, v2, cost; 1090 unsigned i; 1091 1092 for_all_parms (create_default_def, NULL); 1093 1094 map = init_var_map (num_ssa_names); 1095 1096 for_all_parms (register_default_def, NULL); 1097 1098 FOR_EACH_BB_FN (bb, cfun) 1099 { 1100 tree arg; 1101 1102 for (gphi_iterator gpi = gsi_start_phis (bb); 1103 !gsi_end_p (gpi); 1104 gsi_next (&gpi)) 1105 { 1106 gphi *phi = gpi.phi (); 1107 size_t i; 1108 int ver; 1109 tree res; 1110 bool saw_copy = false; 1111 1112 res = gimple_phi_result (phi); 1113 ver = SSA_NAME_VERSION (res); 1114 1115 /* Register ssa_names and coalesces between the args and the result 1116 of all PHI. */ 1117 for (i = 0; i < gimple_phi_num_args (phi); i++) 1118 { 1119 edge e = gimple_phi_arg_edge (phi, i); 1120 arg = PHI_ARG_DEF (phi, i); 1121 if (TREE_CODE (arg) != SSA_NAME) 1122 continue; 1123 1124 if (gimple_can_coalesce_p (arg, res) 1125 || (e->flags & EDGE_ABNORMAL)) 1126 { 1127 saw_copy = true; 1128 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg)); 1129 if ((e->flags & EDGE_ABNORMAL) == 0) 1130 { 1131 int cost = coalesce_cost_edge (e); 1132 if (cost == 1 && has_single_use (arg)) 1133 add_cost_one_coalesce (cl, ver, SSA_NAME_VERSION (arg)); 1134 else 1135 add_coalesce (cl, ver, SSA_NAME_VERSION (arg), cost); 1136 } 1137 } 1138 } 1139 if (saw_copy) 1140 bitmap_set_bit (used_in_copy, ver); 1141 } 1142 1143 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1144 { 1145 stmt = gsi_stmt (gsi); 1146 1147 if (is_gimple_debug (stmt)) 1148 continue; 1149 1150 /* Check for copy coalesces. */ 1151 switch (gimple_code (stmt)) 1152 { 1153 case GIMPLE_ASSIGN: 1154 { 1155 tree lhs = gimple_assign_lhs (stmt); 1156 tree rhs1 = gimple_assign_rhs1 (stmt); 1157 if (gimple_assign_ssa_name_copy_p (stmt) 1158 && gimple_can_coalesce_p (lhs, rhs1)) 1159 { 1160 v1 = SSA_NAME_VERSION (lhs); 1161 v2 = SSA_NAME_VERSION (rhs1); 1162 cost = coalesce_cost_bb (bb); 1163 add_coalesce (cl, v1, v2, cost); 1164 bitmap_set_bit (used_in_copy, v1); 1165 bitmap_set_bit (used_in_copy, v2); 1166 } 1167 } 1168 break; 1169 1170 case GIMPLE_RETURN: 1171 { 1172 tree res = DECL_RESULT (current_function_decl); 1173 if (VOID_TYPE_P (TREE_TYPE (res)) 1174 || !is_gimple_reg (res)) 1175 break; 1176 tree rhs1 = gimple_return_retval (as_a <greturn *> (stmt)); 1177 if (!rhs1) 1178 break; 1179 tree lhs = ssa_default_def (cfun, res); 1180 gcc_assert (lhs); 1181 if (TREE_CODE (rhs1) == SSA_NAME 1182 && gimple_can_coalesce_p (lhs, rhs1)) 1183 { 1184 v1 = SSA_NAME_VERSION (lhs); 1185 v2 = SSA_NAME_VERSION (rhs1); 1186 cost = coalesce_cost_bb (bb); 1187 add_coalesce (cl, v1, v2, cost); 1188 bitmap_set_bit (used_in_copy, v1); 1189 bitmap_set_bit (used_in_copy, v2); 1190 } 1191 break; 1192 } 1193 1194 case GIMPLE_ASM: 1195 { 1196 gasm *asm_stmt = as_a <gasm *> (stmt); 1197 unsigned long noutputs, i; 1198 unsigned long ninputs; 1199 tree *outputs, link; 1200 noutputs = gimple_asm_noutputs (asm_stmt); 1201 ninputs = gimple_asm_ninputs (asm_stmt); 1202 outputs = (tree *) alloca (noutputs * sizeof (tree)); 1203 for (i = 0; i < noutputs; ++i) 1204 { 1205 link = gimple_asm_output_op (asm_stmt, i); 1206 outputs[i] = TREE_VALUE (link); 1207 } 1208 1209 for (i = 0; i < ninputs; ++i) 1210 { 1211 const char *constraint; 1212 tree input; 1213 char *end; 1214 unsigned long match; 1215 1216 link = gimple_asm_input_op (asm_stmt, i); 1217 constraint 1218 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 1219 input = TREE_VALUE (link); 1220 1221 if (TREE_CODE (input) != SSA_NAME) 1222 continue; 1223 1224 match = strtoul (constraint, &end, 10); 1225 if (match >= noutputs || end == constraint) 1226 continue; 1227 1228 if (TREE_CODE (outputs[match]) != SSA_NAME) 1229 continue; 1230 1231 v1 = SSA_NAME_VERSION (outputs[match]); 1232 v2 = SSA_NAME_VERSION (input); 1233 1234 if (gimple_can_coalesce_p (outputs[match], input)) 1235 { 1236 cost = coalesce_cost (REG_BR_PROB_BASE, 1237 optimize_bb_for_size_p (bb)); 1238 add_coalesce (cl, v1, v2, cost); 1239 bitmap_set_bit (used_in_copy, v1); 1240 bitmap_set_bit (used_in_copy, v2); 1241 } 1242 } 1243 break; 1244 } 1245 1246 default: 1247 break; 1248 } 1249 } 1250 } 1251 1252 /* Now process result decls and live on entry variables for entry into 1253 the coalesce list. */ 1254 first = NULL_TREE; 1255 FOR_EACH_SSA_NAME (i, var, cfun) 1256 { 1257 if (!virtual_operand_p (var)) 1258 { 1259 coalesce_with_default (var, cl, used_in_copy); 1260 1261 /* Add coalesces between all the result decls. */ 1262 if (SSA_NAME_VAR (var) 1263 && TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL) 1264 { 1265 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); 1266 if (first == NULL_TREE) 1267 first = var; 1268 else 1269 { 1270 gcc_assert (gimple_can_coalesce_p (var, first)); 1271 v1 = SSA_NAME_VERSION (first); 1272 v2 = SSA_NAME_VERSION (var); 1273 cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)); 1274 add_coalesce (cl, v1, v2, cost); 1275 } 1276 } 1277 /* Mark any default_def variables as being in the coalesce list 1278 since they will have to be coalesced with the base variable. If 1279 not marked as present, they won't be in the coalesce view. */ 1280 if (SSA_NAME_IS_DEFAULT_DEF (var) 1281 && (!has_zero_uses (var) 1282 || (SSA_NAME_VAR (var) 1283 && !VAR_P (SSA_NAME_VAR (var))))) 1284 bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); 1285 } 1286 } 1287 1288 return map; 1289 } 1290 1291 1292 /* Attempt to coalesce ssa versions X and Y together using the partition 1293 mapping in MAP and checking conflicts in GRAPH. Output any debug info to 1294 DEBUG, if it is nun-NULL. */ 1295 1296 static inline bool 1297 attempt_coalesce (var_map map, ssa_conflicts *graph, int x, int y, 1298 FILE *debug) 1299 { 1300 int z; 1301 tree var1, var2; 1302 int p1, p2; 1303 1304 p1 = var_to_partition (map, ssa_name (x)); 1305 p2 = var_to_partition (map, ssa_name (y)); 1306 1307 if (debug) 1308 { 1309 fprintf (debug, "(%d)", x); 1310 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM); 1311 fprintf (debug, " & (%d)", y); 1312 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM); 1313 } 1314 1315 if (p1 == p2) 1316 { 1317 if (debug) 1318 fprintf (debug, ": Already Coalesced.\n"); 1319 return true; 1320 } 1321 1322 if (debug) 1323 fprintf (debug, " [map: %d, %d] ", p1, p2); 1324 1325 1326 if (!ssa_conflicts_test_p (graph, p1, p2)) 1327 { 1328 var1 = partition_to_var (map, p1); 1329 var2 = partition_to_var (map, p2); 1330 1331 z = var_union (map, var1, var2); 1332 if (z == NO_PARTITION) 1333 { 1334 if (debug) 1335 fprintf (debug, ": Unable to perform partition union.\n"); 1336 return false; 1337 } 1338 1339 /* z is the new combined partition. Remove the other partition from 1340 the list, and merge the conflicts. */ 1341 if (z == p1) 1342 ssa_conflicts_merge (graph, p1, p2); 1343 else 1344 ssa_conflicts_merge (graph, p2, p1); 1345 1346 if (debug) 1347 fprintf (debug, ": Success -> %d\n", z); 1348 1349 return true; 1350 } 1351 1352 if (debug) 1353 fprintf (debug, ": Fail due to conflict\n"); 1354 1355 return false; 1356 } 1357 1358 1359 /* Attempt to Coalesce partitions in MAP which occur in the list CL using 1360 GRAPH. Debug output is sent to DEBUG if it is non-NULL. */ 1361 1362 static void 1363 coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, 1364 FILE *debug) 1365 { 1366 int x = 0, y = 0; 1367 tree var1, var2; 1368 int cost; 1369 basic_block bb; 1370 edge e; 1371 edge_iterator ei; 1372 1373 /* First, coalesce all the copies across abnormal edges. These are not placed 1374 in the coalesce list because they do not need to be sorted, and simply 1375 consume extra memory/compilation time in large programs. */ 1376 1377 FOR_EACH_BB_FN (bb, cfun) 1378 { 1379 FOR_EACH_EDGE (e, ei, bb->preds) 1380 if (e->flags & EDGE_ABNORMAL) 1381 { 1382 gphi_iterator gsi; 1383 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 1384 gsi_next (&gsi)) 1385 { 1386 gphi *phi = gsi.phi (); 1387 tree arg = PHI_ARG_DEF (phi, e->dest_idx); 1388 if (SSA_NAME_IS_DEFAULT_DEF (arg) 1389 && (!SSA_NAME_VAR (arg) 1390 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL)) 1391 continue; 1392 1393 tree res = PHI_RESULT (phi); 1394 int v1 = SSA_NAME_VERSION (res); 1395 int v2 = SSA_NAME_VERSION (arg); 1396 1397 if (debug) 1398 fprintf (debug, "Abnormal coalesce: "); 1399 1400 if (!attempt_coalesce (map, graph, v1, v2, debug)) 1401 fail_abnormal_edge_coalesce (v1, v2); 1402 } 1403 } 1404 } 1405 1406 /* Now process the items in the coalesce list. */ 1407 1408 while ((cost = pop_best_coalesce (cl, &x, &y)) != NO_BEST_COALESCE) 1409 { 1410 var1 = ssa_name (x); 1411 var2 = ssa_name (y); 1412 1413 /* Assert the coalesces have the same base variable. */ 1414 gcc_assert (gimple_can_coalesce_p (var1, var2)); 1415 1416 if (debug) 1417 fprintf (debug, "Coalesce list: "); 1418 attempt_coalesce (map, graph, x, y, debug); 1419 } 1420 } 1421 1422 1423 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */ 1424 1425 struct ssa_name_var_hash : nofree_ptr_hash <tree_node> 1426 { 1427 static inline hashval_t hash (const tree_node *); 1428 static inline int equal (const tree_node *, const tree_node *); 1429 }; 1430 1431 inline hashval_t 1432 ssa_name_var_hash::hash (const_tree n) 1433 { 1434 return DECL_UID (SSA_NAME_VAR (n)); 1435 } 1436 1437 inline int 1438 ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2) 1439 { 1440 return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); 1441 } 1442 1443 1444 /* Output partition map MAP with coalescing plan PART to file F. */ 1445 1446 void 1447 dump_part_var_map (FILE *f, partition part, var_map map) 1448 { 1449 int t; 1450 unsigned x, y; 1451 int p; 1452 1453 fprintf (f, "\nCoalescible Partition map \n\n"); 1454 1455 for (x = 0; x < map->num_partitions; x++) 1456 { 1457 if (map->view_to_partition != NULL) 1458 p = map->view_to_partition[x]; 1459 else 1460 p = x; 1461 1462 if (ssa_name (p) == NULL_TREE 1463 || virtual_operand_p (ssa_name (p))) 1464 continue; 1465 1466 t = 0; 1467 for (y = 1; y < num_ssa_names; y++) 1468 { 1469 tree var = version_to_var (map, y); 1470 if (!var) 1471 continue; 1472 int q = var_to_partition (map, var); 1473 p = partition_find (part, q); 1474 gcc_assert (map->partition_to_base_index[q] 1475 == map->partition_to_base_index[p]); 1476 1477 if (p == (int)x) 1478 { 1479 if (t++ == 0) 1480 { 1481 fprintf (f, "Partition %d, base %d (", x, 1482 map->partition_to_base_index[q]); 1483 print_generic_expr (f, partition_to_var (map, q), TDF_SLIM); 1484 fprintf (f, " - "); 1485 } 1486 fprintf (f, "%d ", y); 1487 } 1488 } 1489 if (t != 0) 1490 fprintf (f, ")\n"); 1491 } 1492 fprintf (f, "\n"); 1493 } 1494 1495 /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for 1496 coalescing together, false otherwise. 1497 1498 This must stay consistent with compute_samebase_partition_bases and 1499 compute_optimized_partition_bases. */ 1500 1501 bool 1502 gimple_can_coalesce_p (tree name1, tree name2) 1503 { 1504 /* First check the SSA_NAME's associated DECL. Without 1505 optimization, we only want to coalesce if they have the same DECL 1506 or both have no associated DECL. */ 1507 tree var1 = SSA_NAME_VAR (name1); 1508 tree var2 = SSA_NAME_VAR (name2); 1509 var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE; 1510 var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE; 1511 if (var1 != var2 && !flag_tree_coalesce_vars) 1512 return false; 1513 1514 /* Now check the types. If the types are the same, then we should 1515 try to coalesce V1 and V2. */ 1516 tree t1 = TREE_TYPE (name1); 1517 tree t2 = TREE_TYPE (name2); 1518 if (t1 == t2) 1519 { 1520 check_modes: 1521 /* If the base variables are the same, we're good: none of the 1522 other tests below could possibly fail. */ 1523 var1 = SSA_NAME_VAR (name1); 1524 var2 = SSA_NAME_VAR (name2); 1525 if (var1 == var2) 1526 return true; 1527 1528 /* We don't want to coalesce two SSA names if one of the base 1529 variables is supposed to be a register while the other is 1530 supposed to be on the stack. Anonymous SSA names most often 1531 take registers, but when not optimizing, user variables 1532 should go on the stack, so coalescing them with the anonymous 1533 variable as the partition leader would end up assigning the 1534 user variable to a register. Don't do that! */ 1535 bool reg1 = use_register_for_decl (name1); 1536 bool reg2 = use_register_for_decl (name2); 1537 if (reg1 != reg2) 1538 return false; 1539 1540 /* Check that the promoted modes and unsignedness are the same. 1541 We don't want to coalesce if the promoted modes would be 1542 different, or if they would sign-extend differently. Only 1543 PARM_DECLs and RESULT_DECLs have different promotion rules, 1544 so skip the test if both are variables, or both are anonymous 1545 SSA_NAMEs. */ 1546 int unsigned1, unsigned2; 1547 return ((!var1 || VAR_P (var1)) && (!var2 || VAR_P (var2))) 1548 || ((promote_ssa_mode (name1, &unsigned1) 1549 == promote_ssa_mode (name2, &unsigned2)) 1550 && unsigned1 == unsigned2); 1551 } 1552 1553 /* If alignment requirements are different, we can't coalesce. */ 1554 if (MINIMUM_ALIGNMENT (t1, 1555 var1 ? DECL_MODE (var1) : TYPE_MODE (t1), 1556 var1 ? LOCAL_DECL_ALIGNMENT (var1) : TYPE_ALIGN (t1)) 1557 != MINIMUM_ALIGNMENT (t2, 1558 var2 ? DECL_MODE (var2) : TYPE_MODE (t2), 1559 var2 ? LOCAL_DECL_ALIGNMENT (var2) : TYPE_ALIGN (t2))) 1560 return false; 1561 1562 /* If the types are not the same, see whether they are compatible. This 1563 (for example) allows coalescing when the types are fundamentally the 1564 same, but just have different names. */ 1565 if (types_compatible_p (t1, t2)) 1566 goto check_modes; 1567 1568 return false; 1569 } 1570 1571 /* Fill in MAP's partition_to_base_index, with one index for each 1572 partition of SSA names USED_IN_COPIES and related by CL coalesce 1573 possibilities. This must match gimple_can_coalesce_p in the 1574 optimized case. */ 1575 1576 static void 1577 compute_optimized_partition_bases (var_map map, bitmap used_in_copies, 1578 coalesce_list *cl) 1579 { 1580 int parts = num_var_partitions (map); 1581 partition tentative = partition_new (parts); 1582 1583 /* Partition the SSA versions so that, for each coalescible 1584 pair, both of its members are in the same partition in 1585 TENTATIVE. */ 1586 gcc_assert (!cl->sorted); 1587 coalesce_pair *node; 1588 coalesce_iterator_type ppi; 1589 FOR_EACH_PARTITION_PAIR (node, ppi, cl) 1590 { 1591 tree v1 = ssa_name (node->first_element); 1592 int p1 = partition_find (tentative, var_to_partition (map, v1)); 1593 tree v2 = ssa_name (node->second_element); 1594 int p2 = partition_find (tentative, var_to_partition (map, v2)); 1595 1596 if (p1 == p2) 1597 continue; 1598 1599 partition_union (tentative, p1, p2); 1600 } 1601 1602 /* We have to deal with cost one pairs too. */ 1603 for (cost_one_pair *co = cl->cost_one_list; co; co = co->next) 1604 { 1605 tree v1 = ssa_name (co->first_element); 1606 int p1 = partition_find (tentative, var_to_partition (map, v1)); 1607 tree v2 = ssa_name (co->second_element); 1608 int p2 = partition_find (tentative, var_to_partition (map, v2)); 1609 1610 if (p1 == p2) 1611 continue; 1612 1613 partition_union (tentative, p1, p2); 1614 } 1615 1616 /* And also with abnormal edges. */ 1617 basic_block bb; 1618 edge e; 1619 edge_iterator ei; 1620 FOR_EACH_BB_FN (bb, cfun) 1621 { 1622 FOR_EACH_EDGE (e, ei, bb->preds) 1623 if (e->flags & EDGE_ABNORMAL) 1624 { 1625 gphi_iterator gsi; 1626 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 1627 gsi_next (&gsi)) 1628 { 1629 gphi *phi = gsi.phi (); 1630 tree arg = PHI_ARG_DEF (phi, e->dest_idx); 1631 if (SSA_NAME_IS_DEFAULT_DEF (arg) 1632 && (!SSA_NAME_VAR (arg) 1633 || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL)) 1634 continue; 1635 1636 tree res = PHI_RESULT (phi); 1637 1638 int p1 = partition_find (tentative, var_to_partition (map, res)); 1639 int p2 = partition_find (tentative, var_to_partition (map, arg)); 1640 1641 if (p1 == p2) 1642 continue; 1643 1644 partition_union (tentative, p1, p2); 1645 } 1646 } 1647 } 1648 1649 map->partition_to_base_index = XCNEWVEC (int, parts); 1650 auto_vec<unsigned int> index_map (parts); 1651 if (parts) 1652 index_map.quick_grow (parts); 1653 1654 const unsigned no_part = -1; 1655 unsigned count = parts; 1656 while (count) 1657 index_map[--count] = no_part; 1658 1659 /* Initialize MAP's mapping from partition to base index, using 1660 as base indices an enumeration of the TENTATIVE partitions in 1661 which each SSA version ended up, so that we compute conflicts 1662 between all SSA versions that ended up in the same potential 1663 coalesce partition. */ 1664 bitmap_iterator bi; 1665 unsigned i; 1666 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi) 1667 { 1668 int pidx = var_to_partition (map, ssa_name (i)); 1669 int base = partition_find (tentative, pidx); 1670 if (index_map[base] != no_part) 1671 continue; 1672 index_map[base] = count++; 1673 } 1674 1675 map->num_basevars = count; 1676 1677 EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi) 1678 { 1679 int pidx = var_to_partition (map, ssa_name (i)); 1680 int base = partition_find (tentative, pidx); 1681 gcc_assert (index_map[base] < count); 1682 map->partition_to_base_index[pidx] = index_map[base]; 1683 } 1684 1685 if (dump_file && (dump_flags & TDF_DETAILS)) 1686 dump_part_var_map (dump_file, tentative, map); 1687 1688 partition_delete (tentative); 1689 } 1690 1691 /* Reduce the number of copies by coalescing variables in the function. Return 1692 a partition map with the resulting coalesces. */ 1693 1694 extern var_map 1695 coalesce_ssa_name (void) 1696 { 1697 tree_live_info_p liveinfo; 1698 ssa_conflicts *graph; 1699 coalesce_list *cl; 1700 auto_bitmap used_in_copies; 1701 var_map map; 1702 unsigned int i; 1703 tree a; 1704 1705 cl = create_coalesce_list (); 1706 map = create_outofssa_var_map (cl, used_in_copies); 1707 1708 /* If this optimization is disabled, we need to coalesce all the 1709 names originating from the same SSA_NAME_VAR so debug info 1710 remains undisturbed. */ 1711 if (!flag_tree_coalesce_vars) 1712 { 1713 hash_table<ssa_name_var_hash> ssa_name_hash (10); 1714 1715 FOR_EACH_SSA_NAME (i, a, cfun) 1716 { 1717 if (SSA_NAME_VAR (a) 1718 && !DECL_IGNORED_P (SSA_NAME_VAR (a)) 1719 && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a) 1720 || !VAR_P (SSA_NAME_VAR (a)))) 1721 { 1722 tree *slot = ssa_name_hash.find_slot (a, INSERT); 1723 1724 if (!*slot) 1725 *slot = a; 1726 else 1727 { 1728 /* If the variable is a PARM_DECL or a RESULT_DECL, we 1729 _require_ that all the names originating from it be 1730 coalesced, because there must be a single partition 1731 containing all the names so that it can be assigned 1732 the canonical RTL location of the DECL safely. 1733 If in_lto_p, a function could have been compiled 1734 originally with optimizations and only the link 1735 performed at -O0, so we can't actually require it. */ 1736 const int cost 1737 = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p) 1738 ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST; 1739 add_coalesce (cl, SSA_NAME_VERSION (a), 1740 SSA_NAME_VERSION (*slot), cost); 1741 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a)); 1742 bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot)); 1743 } 1744 } 1745 } 1746 } 1747 if (dump_file && (dump_flags & TDF_DETAILS)) 1748 dump_var_map (dump_file, map); 1749 1750 partition_view_bitmap (map, used_in_copies); 1751 1752 compute_optimized_partition_bases (map, used_in_copies, cl); 1753 1754 if (num_var_partitions (map) < 1) 1755 { 1756 delete_coalesce_list (cl); 1757 return map; 1758 } 1759 1760 if (dump_file && (dump_flags & TDF_DETAILS)) 1761 dump_var_map (dump_file, map); 1762 1763 liveinfo = calculate_live_ranges (map, false); 1764 1765 if (dump_file && (dump_flags & TDF_DETAILS)) 1766 dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY); 1767 1768 /* Build a conflict graph. */ 1769 graph = build_ssa_conflict_graph (liveinfo); 1770 delete_tree_live_info (liveinfo); 1771 if (dump_file && (dump_flags & TDF_DETAILS)) 1772 ssa_conflicts_dump (dump_file, graph); 1773 1774 sort_coalesce_list (cl, graph, map); 1775 1776 if (dump_file && (dump_flags & TDF_DETAILS)) 1777 { 1778 fprintf (dump_file, "\nAfter sorting:\n"); 1779 dump_coalesce_list (dump_file, cl); 1780 } 1781 1782 /* First, coalesce all live on entry variables to their base variable. 1783 This will ensure the first use is coming from the correct location. */ 1784 1785 if (dump_file && (dump_flags & TDF_DETAILS)) 1786 dump_var_map (dump_file, map); 1787 1788 /* Now coalesce everything in the list. */ 1789 coalesce_partitions (map, graph, cl, 1790 ((dump_flags & TDF_DETAILS) ? dump_file : NULL)); 1791 1792 delete_coalesce_list (cl); 1793 ssa_conflicts_delete (graph); 1794 1795 return map; 1796 } 1797 1798 /* We need to pass two arguments to set_parm_default_def_partition, 1799 but for_all_parms only supports one. Use a pair. */ 1800 1801 typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; 1802 1803 /* Set in ARG's PARTS bitmap the bit corresponding to the partition in 1804 ARG's MAP containing VAR's default def. */ 1805 1806 static void 1807 set_parm_default_def_partition (tree var, void *arg_) 1808 { 1809 parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; 1810 var_map map = arg->first; 1811 bitmap parts = arg->second; 1812 1813 if (!is_gimple_reg (var)) 1814 return; 1815 1816 tree ssa = ssa_default_def (cfun, var); 1817 gcc_assert (ssa); 1818 1819 int version = var_to_partition (map, ssa); 1820 gcc_assert (version != NO_PARTITION); 1821 1822 bool changed = bitmap_set_bit (parts, version); 1823 gcc_assert (changed); 1824 } 1825 1826 /* Allocate and return a bitmap that has a bit set for each partition 1827 that contains a default def for a parameter. */ 1828 1829 bitmap 1830 get_parm_default_def_partitions (var_map map) 1831 { 1832 bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); 1833 1834 parm_default_def_partition_arg 1835 arg = std::make_pair (map, parm_default_def_parts); 1836 1837 for_all_parms (set_parm_default_def_partition, &arg); 1838 1839 return parm_default_def_parts; 1840 } 1841 1842 /* Allocate and return a bitmap that has a bit set for each partition 1843 that contains an undefined value. */ 1844 1845 bitmap 1846 get_undefined_value_partitions (var_map map) 1847 { 1848 bitmap undefined_value_parts = BITMAP_ALLOC (NULL); 1849 1850 for (unsigned int i = 1; i < num_ssa_names; i++) 1851 { 1852 tree var = ssa_name (i); 1853 if (var 1854 && !virtual_operand_p (var) 1855 && !has_zero_uses (var) 1856 && ssa_undefined_value_p (var)) 1857 { 1858 const int p = var_to_partition (map, var); 1859 if (p != NO_PARTITION) 1860 bitmap_set_bit (undefined_value_parts, p); 1861 } 1862 } 1863 1864 return undefined_value_parts; 1865 } 1866