1/* IRA allocation based on graph coloring. 2 Copyright (C) 2006-2015 Free Software Foundation, Inc. 3 Contributed by Vladimir Makarov <vmakarov@redhat.com>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for 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 "rtl.h" 26#include "tm_p.h" 27#include "target.h" 28#include "regs.h" 29#include "flags.h" 30#include "sbitmap.h" 31#include "bitmap.h" 32#include "hash-table.h" 33#include "hard-reg-set.h" 34#include "predict.h" 35#include "vec.h" 36#include "hashtab.h" 37#include "hash-set.h" 38#include "machmode.h" 39#include "input.h" 40#include "function.h" 41#include "dominance.h" 42#include "cfg.h" 43#include "basic-block.h" 44#include "symtab.h" 45#include "statistics.h" 46#include "double-int.h" 47#include "real.h" 48#include "fixed-value.h" 49#include "alias.h" 50#include "wide-int.h" 51#include "inchash.h" 52#include "tree.h" 53#include "insn-config.h" 54#include "expmed.h" 55#include "dojump.h" 56#include "explow.h" 57#include "calls.h" 58#include "emit-rtl.h" 59#include "varasm.h" 60#include "stmt.h" 61#include "expr.h" 62#include "diagnostic-core.h" 63#include "reload.h" 64#include "params.h" 65#include "df.h" 66#include "recog.h" 67#include "ira-int.h" 68 69typedef struct allocno_hard_regs *allocno_hard_regs_t; 70 71/* The structure contains information about hard registers can be 72 assigned to allocnos. Usually it is allocno profitable hard 73 registers but in some cases this set can be a bit different. Major 74 reason of the difference is a requirement to use hard register sets 75 that form a tree or a forest (set of trees), i.e. hard register set 76 of a node should contain hard register sets of its subnodes. */ 77struct allocno_hard_regs 78{ 79 /* Hard registers can be assigned to an allocno. */ 80 HARD_REG_SET set; 81 /* Overall (spilling) cost of all allocnos with given register 82 set. */ 83 int64_t cost; 84}; 85 86typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t; 87 88/* A node representing allocno hard registers. Such nodes form a 89 forest (set of trees). Each subnode of given node in the forest 90 refers for hard register set (usually allocno profitable hard 91 register set) which is a subset of one referred from given 92 node. */ 93struct allocno_hard_regs_node 94{ 95 /* Set up number of the node in preorder traversing of the forest. */ 96 int preorder_num; 97 /* Used for different calculation like finding conflict size of an 98 allocno. */ 99 int check; 100 /* Used for calculation of conflict size of an allocno. The 101 conflict size of the allocno is maximal number of given allocno 102 hard registers needed for allocation of the conflicting allocnos. 103 Given allocno is trivially colored if this number plus the number 104 of hard registers needed for given allocno is not greater than 105 the number of given allocno hard register set. */ 106 int conflict_size; 107 /* The number of hard registers given by member hard_regs. */ 108 int hard_regs_num; 109 /* The following member is used to form the final forest. */ 110 bool used_p; 111 /* Pointer to the corresponding profitable hard registers. */ 112 allocno_hard_regs_t hard_regs; 113 /* Parent, first subnode, previous and next node with the same 114 parent in the forest. */ 115 allocno_hard_regs_node_t parent, first, prev, next; 116}; 117 118/* Info about changing hard reg costs of an allocno. */ 119struct update_cost_record 120{ 121 /* Hard regno for which we changed the cost. */ 122 int hard_regno; 123 /* Divisor used when we changed the cost of HARD_REGNO. */ 124 int divisor; 125 /* Next record for given allocno. */ 126 struct update_cost_record *next; 127}; 128 129/* To decrease footprint of ira_allocno structure we store all data 130 needed only for coloring in the following structure. */ 131struct allocno_color_data 132{ 133 /* TRUE value means that the allocno was not removed yet from the 134 conflicting graph during coloring. */ 135 unsigned int in_graph_p : 1; 136 /* TRUE if it is put on the stack to make other allocnos 137 colorable. */ 138 unsigned int may_be_spilled_p : 1; 139 /* TRUE if the allocno is trivially colorable. */ 140 unsigned int colorable_p : 1; 141 /* Number of hard registers of the allocno class really 142 available for the allocno allocation. It is number of the 143 profitable hard regs. */ 144 int available_regs_num; 145 /* Allocnos in a bucket (used in coloring) chained by the following 146 two members. */ 147 ira_allocno_t next_bucket_allocno; 148 ira_allocno_t prev_bucket_allocno; 149 /* Used for temporary purposes. */ 150 int temp; 151 /* Used to exclude repeated processing. */ 152 int last_process; 153 /* Profitable hard regs available for this pseudo allocation. It 154 means that the set excludes unavailable hard regs and hard regs 155 conflicting with given pseudo. They should be of the allocno 156 class. */ 157 HARD_REG_SET profitable_hard_regs; 158 /* The allocno hard registers node. */ 159 allocno_hard_regs_node_t hard_regs_node; 160 /* Array of structures allocno_hard_regs_subnode representing 161 given allocno hard registers node (the 1st element in the array) 162 and all its subnodes in the tree (forest) of allocno hard 163 register nodes (see comments above). */ 164 int hard_regs_subnodes_start; 165 /* The length of the previous array. */ 166 int hard_regs_subnodes_num; 167 /* Records about updating allocno hard reg costs from copies. If 168 the allocno did not get expected hard register, these records are 169 used to restore original hard reg costs of allocnos connected to 170 this allocno by copies. */ 171 struct update_cost_record *update_cost_records; 172 /* Threads. We collect allocnos connected by copies into threads 173 and try to assign hard regs to allocnos by threads. */ 174 /* Allocno representing all thread. */ 175 ira_allocno_t first_thread_allocno; 176 /* Allocnos in thread forms a cycle list through the following 177 member. */ 178 ira_allocno_t next_thread_allocno; 179 /* All thread frequency. Defined only for first thread allocno. */ 180 int thread_freq; 181}; 182 183/* See above. */ 184typedef struct allocno_color_data *allocno_color_data_t; 185 186/* Container for storing allocno data concerning coloring. */ 187static allocno_color_data_t allocno_color_data; 188 189/* Macro to access the data concerning coloring. */ 190#define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a)) 191 192/* Used for finding allocno colorability to exclude repeated allocno 193 processing and for updating preferencing to exclude repeated 194 allocno processing during assignment. */ 195static int curr_allocno_process; 196 197/* This file contains code for regional graph coloring, spill/restore 198 code placement optimization, and code helping the reload pass to do 199 a better job. */ 200 201/* Bitmap of allocnos which should be colored. */ 202static bitmap coloring_allocno_bitmap; 203 204/* Bitmap of allocnos which should be taken into account during 205 coloring. In general case it contains allocnos from 206 coloring_allocno_bitmap plus other already colored conflicting 207 allocnos. */ 208static bitmap consideration_allocno_bitmap; 209 210/* All allocnos sorted according their priorities. */ 211static ira_allocno_t *sorted_allocnos; 212 213/* Vec representing the stack of allocnos used during coloring. */ 214static vec<ira_allocno_t> allocno_stack_vec; 215 216/* Helper for qsort comparison callbacks - return a positive integer if 217 X > Y, or a negative value otherwise. Use a conditional expression 218 instead of a difference computation to insulate from possible overflow 219 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */ 220#define SORTGT(x,y) (((x) > (y)) ? 1 : -1) 221 222 223 224/* Definition of vector of allocno hard registers. */ 225 226/* Vector of unique allocno hard registers. */ 227static vec<allocno_hard_regs_t> allocno_hard_regs_vec; 228 229struct allocno_hard_regs_hasher : typed_noop_remove <allocno_hard_regs> 230{ 231 typedef allocno_hard_regs value_type; 232 typedef allocno_hard_regs compare_type; 233 static inline hashval_t hash (const value_type *); 234 static inline bool equal (const value_type *, const compare_type *); 235}; 236 237/* Returns hash value for allocno hard registers V. */ 238inline hashval_t 239allocno_hard_regs_hasher::hash (const value_type *hv) 240{ 241 return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0); 242} 243 244/* Compares allocno hard registers V1 and V2. */ 245inline bool 246allocno_hard_regs_hasher::equal (const value_type *hv1, const compare_type *hv2) 247{ 248 return hard_reg_set_equal_p (hv1->set, hv2->set); 249} 250 251/* Hash table of unique allocno hard registers. */ 252static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab; 253 254/* Return allocno hard registers in the hash table equal to HV. */ 255static allocno_hard_regs_t 256find_hard_regs (allocno_hard_regs_t hv) 257{ 258 return allocno_hard_regs_htab->find (hv); 259} 260 261/* Insert allocno hard registers HV in the hash table (if it is not 262 there yet) and return the value which in the table. */ 263static allocno_hard_regs_t 264insert_hard_regs (allocno_hard_regs_t hv) 265{ 266 allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT); 267 268 if (*slot == NULL) 269 *slot = hv; 270 return *slot; 271} 272 273/* Initialize data concerning allocno hard registers. */ 274static void 275init_allocno_hard_regs (void) 276{ 277 allocno_hard_regs_vec.create (200); 278 allocno_hard_regs_htab 279 = new hash_table<allocno_hard_regs_hasher> (200); 280} 281 282/* Add (or update info about) allocno hard registers with SET and 283 COST. */ 284static allocno_hard_regs_t 285add_allocno_hard_regs (HARD_REG_SET set, int64_t cost) 286{ 287 struct allocno_hard_regs temp; 288 allocno_hard_regs_t hv; 289 290 gcc_assert (! hard_reg_set_empty_p (set)); 291 COPY_HARD_REG_SET (temp.set, set); 292 if ((hv = find_hard_regs (&temp)) != NULL) 293 hv->cost += cost; 294 else 295 { 296 hv = ((struct allocno_hard_regs *) 297 ira_allocate (sizeof (struct allocno_hard_regs))); 298 COPY_HARD_REG_SET (hv->set, set); 299 hv->cost = cost; 300 allocno_hard_regs_vec.safe_push (hv); 301 insert_hard_regs (hv); 302 } 303 return hv; 304} 305 306/* Finalize data concerning allocno hard registers. */ 307static void 308finish_allocno_hard_regs (void) 309{ 310 int i; 311 allocno_hard_regs_t hv; 312 313 for (i = 0; 314 allocno_hard_regs_vec.iterate (i, &hv); 315 i++) 316 ira_free (hv); 317 delete allocno_hard_regs_htab; 318 allocno_hard_regs_htab = NULL; 319 allocno_hard_regs_vec.release (); 320} 321 322/* Sort hard regs according to their frequency of usage. */ 323static int 324allocno_hard_regs_compare (const void *v1p, const void *v2p) 325{ 326 allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p; 327 allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p; 328 329 if (hv2->cost > hv1->cost) 330 return 1; 331 else if (hv2->cost < hv1->cost) 332 return -1; 333 else 334 return 0; 335} 336 337 338 339/* Used for finding a common ancestor of two allocno hard registers 340 nodes in the forest. We use the current value of 341 'node_check_tick' to mark all nodes from one node to the top and 342 then walking up from another node until we find a marked node. 343 344 It is also used to figure out allocno colorability as a mark that 345 we already reset value of member 'conflict_size' for the forest 346 node corresponding to the processed allocno. */ 347static int node_check_tick; 348 349/* Roots of the forest containing hard register sets can be assigned 350 to allocnos. */ 351static allocno_hard_regs_node_t hard_regs_roots; 352 353/* Definition of vector of allocno hard register nodes. */ 354 355/* Vector used to create the forest. */ 356static vec<allocno_hard_regs_node_t> hard_regs_node_vec; 357 358/* Create and return allocno hard registers node containing allocno 359 hard registers HV. */ 360static allocno_hard_regs_node_t 361create_new_allocno_hard_regs_node (allocno_hard_regs_t hv) 362{ 363 allocno_hard_regs_node_t new_node; 364 365 new_node = ((struct allocno_hard_regs_node *) 366 ira_allocate (sizeof (struct allocno_hard_regs_node))); 367 new_node->check = 0; 368 new_node->hard_regs = hv; 369 new_node->hard_regs_num = hard_reg_set_size (hv->set); 370 new_node->first = NULL; 371 new_node->used_p = false; 372 return new_node; 373} 374 375/* Add allocno hard registers node NEW_NODE to the forest on its level 376 given by ROOTS. */ 377static void 378add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots, 379 allocno_hard_regs_node_t new_node) 380{ 381 new_node->next = *roots; 382 if (new_node->next != NULL) 383 new_node->next->prev = new_node; 384 new_node->prev = NULL; 385 *roots = new_node; 386} 387 388/* Add allocno hard registers HV (or its best approximation if it is 389 not possible) to the forest on its level given by ROOTS. */ 390static void 391add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots, 392 allocno_hard_regs_t hv) 393{ 394 unsigned int i, start; 395 allocno_hard_regs_node_t node, prev, new_node; 396 HARD_REG_SET temp_set; 397 allocno_hard_regs_t hv2; 398 399 start = hard_regs_node_vec.length (); 400 for (node = *roots; node != NULL; node = node->next) 401 { 402 if (hard_reg_set_equal_p (hv->set, node->hard_regs->set)) 403 return; 404 if (hard_reg_set_subset_p (hv->set, node->hard_regs->set)) 405 { 406 add_allocno_hard_regs_to_forest (&node->first, hv); 407 return; 408 } 409 if (hard_reg_set_subset_p (node->hard_regs->set, hv->set)) 410 hard_regs_node_vec.safe_push (node); 411 else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set)) 412 { 413 COPY_HARD_REG_SET (temp_set, hv->set); 414 AND_HARD_REG_SET (temp_set, node->hard_regs->set); 415 hv2 = add_allocno_hard_regs (temp_set, hv->cost); 416 add_allocno_hard_regs_to_forest (&node->first, hv2); 417 } 418 } 419 if (hard_regs_node_vec.length () 420 > start + 1) 421 { 422 /* Create a new node which contains nodes in hard_regs_node_vec. */ 423 CLEAR_HARD_REG_SET (temp_set); 424 for (i = start; 425 i < hard_regs_node_vec.length (); 426 i++) 427 { 428 node = hard_regs_node_vec[i]; 429 IOR_HARD_REG_SET (temp_set, node->hard_regs->set); 430 } 431 hv = add_allocno_hard_regs (temp_set, hv->cost); 432 new_node = create_new_allocno_hard_regs_node (hv); 433 prev = NULL; 434 for (i = start; 435 i < hard_regs_node_vec.length (); 436 i++) 437 { 438 node = hard_regs_node_vec[i]; 439 if (node->prev == NULL) 440 *roots = node->next; 441 else 442 node->prev->next = node->next; 443 if (node->next != NULL) 444 node->next->prev = node->prev; 445 if (prev == NULL) 446 new_node->first = node; 447 else 448 prev->next = node; 449 node->prev = prev; 450 node->next = NULL; 451 prev = node; 452 } 453 add_new_allocno_hard_regs_node_to_forest (roots, new_node); 454 } 455 hard_regs_node_vec.truncate (start); 456} 457 458/* Add allocno hard registers nodes starting with the forest level 459 given by FIRST which contains biggest set inside SET. */ 460static void 461collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first, 462 HARD_REG_SET set) 463{ 464 allocno_hard_regs_node_t node; 465 466 ira_assert (first != NULL); 467 for (node = first; node != NULL; node = node->next) 468 if (hard_reg_set_subset_p (node->hard_regs->set, set)) 469 hard_regs_node_vec.safe_push (node); 470 else if (hard_reg_set_intersect_p (set, node->hard_regs->set)) 471 collect_allocno_hard_regs_cover (node->first, set); 472} 473 474/* Set up field parent as PARENT in all allocno hard registers nodes 475 in forest given by FIRST. */ 476static void 477setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first, 478 allocno_hard_regs_node_t parent) 479{ 480 allocno_hard_regs_node_t node; 481 482 for (node = first; node != NULL; node = node->next) 483 { 484 node->parent = parent; 485 setup_allocno_hard_regs_nodes_parent (node->first, node); 486 } 487} 488 489/* Return allocno hard registers node which is a first common ancestor 490 node of FIRST and SECOND in the forest. */ 491static allocno_hard_regs_node_t 492first_common_ancestor_node (allocno_hard_regs_node_t first, 493 allocno_hard_regs_node_t second) 494{ 495 allocno_hard_regs_node_t node; 496 497 node_check_tick++; 498 for (node = first; node != NULL; node = node->parent) 499 node->check = node_check_tick; 500 for (node = second; node != NULL; node = node->parent) 501 if (node->check == node_check_tick) 502 return node; 503 return first_common_ancestor_node (second, first); 504} 505 506/* Print hard reg set SET to F. */ 507static void 508print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p) 509{ 510 int i, start; 511 512 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++) 513 { 514 if (TEST_HARD_REG_BIT (set, i)) 515 { 516 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1)) 517 start = i; 518 } 519 if (start >= 0 520 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i))) 521 { 522 if (start == i - 1) 523 fprintf (f, " %d", start); 524 else if (start == i - 2) 525 fprintf (f, " %d %d", start, start + 1); 526 else 527 fprintf (f, " %d-%d", start, i - 1); 528 start = -1; 529 } 530 } 531 if (new_line_p) 532 fprintf (f, "\n"); 533} 534 535/* Print allocno hard register subforest given by ROOTS and its LEVEL 536 to F. */ 537static void 538print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots, 539 int level) 540{ 541 int i; 542 allocno_hard_regs_node_t node; 543 544 for (node = roots; node != NULL; node = node->next) 545 { 546 fprintf (f, " "); 547 for (i = 0; i < level * 2; i++) 548 fprintf (f, " "); 549 fprintf (f, "%d:(", node->preorder_num); 550 print_hard_reg_set (f, node->hard_regs->set, false); 551 fprintf (f, ")@%"PRId64"\n", node->hard_regs->cost); 552 print_hard_regs_subforest (f, node->first, level + 1); 553 } 554} 555 556/* Print the allocno hard register forest to F. */ 557static void 558print_hard_regs_forest (FILE *f) 559{ 560 fprintf (f, " Hard reg set forest:\n"); 561 print_hard_regs_subforest (f, hard_regs_roots, 1); 562} 563 564/* Print the allocno hard register forest to stderr. */ 565void 566ira_debug_hard_regs_forest (void) 567{ 568 print_hard_regs_forest (stderr); 569} 570 571/* Remove unused allocno hard registers nodes from forest given by its 572 *ROOTS. */ 573static void 574remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots) 575{ 576 allocno_hard_regs_node_t node, prev, next, last; 577 578 for (prev = NULL, node = *roots; node != NULL; node = next) 579 { 580 next = node->next; 581 if (node->used_p) 582 { 583 remove_unused_allocno_hard_regs_nodes (&node->first); 584 prev = node; 585 } 586 else 587 { 588 for (last = node->first; 589 last != NULL && last->next != NULL; 590 last = last->next) 591 ; 592 if (last != NULL) 593 { 594 if (prev == NULL) 595 *roots = node->first; 596 else 597 prev->next = node->first; 598 if (next != NULL) 599 next->prev = last; 600 last->next = next; 601 next = node->first; 602 } 603 else 604 { 605 if (prev == NULL) 606 *roots = next; 607 else 608 prev->next = next; 609 if (next != NULL) 610 next->prev = prev; 611 } 612 ira_free (node); 613 } 614 } 615} 616 617/* Set up fields preorder_num starting with START_NUM in all allocno 618 hard registers nodes in forest given by FIRST. Return biggest set 619 PREORDER_NUM increased by 1. */ 620static int 621enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first, 622 allocno_hard_regs_node_t parent, 623 int start_num) 624{ 625 allocno_hard_regs_node_t node; 626 627 for (node = first; node != NULL; node = node->next) 628 { 629 node->preorder_num = start_num++; 630 node->parent = parent; 631 start_num = enumerate_allocno_hard_regs_nodes (node->first, node, 632 start_num); 633 } 634 return start_num; 635} 636 637/* Number of allocno hard registers nodes in the forest. */ 638static int allocno_hard_regs_nodes_num; 639 640/* Table preorder number of allocno hard registers node in the forest 641 -> the allocno hard registers node. */ 642static allocno_hard_regs_node_t *allocno_hard_regs_nodes; 643 644/* See below. */ 645typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t; 646 647/* The structure is used to describes all subnodes (not only immediate 648 ones) in the mentioned above tree for given allocno hard register 649 node. The usage of such data accelerates calculation of 650 colorability of given allocno. */ 651struct allocno_hard_regs_subnode 652{ 653 /* The conflict size of conflicting allocnos whose hard register 654 sets are equal sets (plus supersets if given node is given 655 allocno hard registers node) of one in the given node. */ 656 int left_conflict_size; 657 /* The summary conflict size of conflicting allocnos whose hard 658 register sets are strict subsets of one in the given node. 659 Overall conflict size is 660 left_conflict_subnodes_size 661 + MIN (max_node_impact - left_conflict_subnodes_size, 662 left_conflict_size) 663 */ 664 short left_conflict_subnodes_size; 665 short max_node_impact; 666}; 667 668/* Container for hard regs subnodes of all allocnos. */ 669static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes; 670 671/* Table (preorder number of allocno hard registers node in the 672 forest, preorder number of allocno hard registers subnode) -> index 673 of the subnode relative to the node. -1 if it is not a 674 subnode. */ 675static int *allocno_hard_regs_subnode_index; 676 677/* Setup arrays ALLOCNO_HARD_REGS_NODES and 678 ALLOCNO_HARD_REGS_SUBNODE_INDEX. */ 679static void 680setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first) 681{ 682 allocno_hard_regs_node_t node, parent; 683 int index; 684 685 for (node = first; node != NULL; node = node->next) 686 { 687 allocno_hard_regs_nodes[node->preorder_num] = node; 688 for (parent = node; parent != NULL; parent = parent->parent) 689 { 690 index = parent->preorder_num * allocno_hard_regs_nodes_num; 691 allocno_hard_regs_subnode_index[index + node->preorder_num] 692 = node->preorder_num - parent->preorder_num; 693 } 694 setup_allocno_hard_regs_subnode_index (node->first); 695 } 696} 697 698/* Count all allocno hard registers nodes in tree ROOT. */ 699static int 700get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root) 701{ 702 int len = 1; 703 704 for (root = root->first; root != NULL; root = root->next) 705 len += get_allocno_hard_regs_subnodes_num (root); 706 return len; 707} 708 709/* Build the forest of allocno hard registers nodes and assign each 710 allocno a node from the forest. */ 711static void 712form_allocno_hard_regs_nodes_forest (void) 713{ 714 unsigned int i, j, size, len; 715 int start; 716 ira_allocno_t a; 717 allocno_hard_regs_t hv; 718 bitmap_iterator bi; 719 HARD_REG_SET temp; 720 allocno_hard_regs_node_t node, allocno_hard_regs_node; 721 allocno_color_data_t allocno_data; 722 723 node_check_tick = 0; 724 init_allocno_hard_regs (); 725 hard_regs_roots = NULL; 726 hard_regs_node_vec.create (100); 727 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 728 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i)) 729 { 730 CLEAR_HARD_REG_SET (temp); 731 SET_HARD_REG_BIT (temp, i); 732 hv = add_allocno_hard_regs (temp, 0); 733 node = create_new_allocno_hard_regs_node (hv); 734 add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node); 735 } 736 start = allocno_hard_regs_vec.length (); 737 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 738 { 739 a = ira_allocnos[i]; 740 allocno_data = ALLOCNO_COLOR_DATA (a); 741 742 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) 743 continue; 744 hv = (add_allocno_hard_regs 745 (allocno_data->profitable_hard_regs, 746 ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a))); 747 } 748 SET_HARD_REG_SET (temp); 749 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs); 750 add_allocno_hard_regs (temp, 0); 751 qsort (allocno_hard_regs_vec.address () + start, 752 allocno_hard_regs_vec.length () - start, 753 sizeof (allocno_hard_regs_t), allocno_hard_regs_compare); 754 for (i = start; 755 allocno_hard_regs_vec.iterate (i, &hv); 756 i++) 757 { 758 add_allocno_hard_regs_to_forest (&hard_regs_roots, hv); 759 ira_assert (hard_regs_node_vec.length () == 0); 760 } 761 /* We need to set up parent fields for right work of 762 first_common_ancestor_node. */ 763 setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL); 764 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 765 { 766 a = ira_allocnos[i]; 767 allocno_data = ALLOCNO_COLOR_DATA (a); 768 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) 769 continue; 770 hard_regs_node_vec.truncate (0); 771 collect_allocno_hard_regs_cover (hard_regs_roots, 772 allocno_data->profitable_hard_regs); 773 allocno_hard_regs_node = NULL; 774 for (j = 0; hard_regs_node_vec.iterate (j, &node); j++) 775 allocno_hard_regs_node 776 = (j == 0 777 ? node 778 : first_common_ancestor_node (node, allocno_hard_regs_node)); 779 /* That is a temporary storage. */ 780 allocno_hard_regs_node->used_p = true; 781 allocno_data->hard_regs_node = allocno_hard_regs_node; 782 } 783 ira_assert (hard_regs_roots->next == NULL); 784 hard_regs_roots->used_p = true; 785 remove_unused_allocno_hard_regs_nodes (&hard_regs_roots); 786 allocno_hard_regs_nodes_num 787 = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0); 788 allocno_hard_regs_nodes 789 = ((allocno_hard_regs_node_t *) 790 ira_allocate (allocno_hard_regs_nodes_num 791 * sizeof (allocno_hard_regs_node_t))); 792 size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num; 793 allocno_hard_regs_subnode_index 794 = (int *) ira_allocate (size * sizeof (int)); 795 for (i = 0; i < size; i++) 796 allocno_hard_regs_subnode_index[i] = -1; 797 setup_allocno_hard_regs_subnode_index (hard_regs_roots); 798 start = 0; 799 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 800 { 801 a = ira_allocnos[i]; 802 allocno_data = ALLOCNO_COLOR_DATA (a); 803 if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs)) 804 continue; 805 len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node); 806 allocno_data->hard_regs_subnodes_start = start; 807 allocno_data->hard_regs_subnodes_num = len; 808 start += len; 809 } 810 allocno_hard_regs_subnodes 811 = ((allocno_hard_regs_subnode_t) 812 ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start)); 813 hard_regs_node_vec.release (); 814} 815 816/* Free tree of allocno hard registers nodes given by its ROOT. */ 817static void 818finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root) 819{ 820 allocno_hard_regs_node_t child, next; 821 822 for (child = root->first; child != NULL; child = next) 823 { 824 next = child->next; 825 finish_allocno_hard_regs_nodes_tree (child); 826 } 827 ira_free (root); 828} 829 830/* Finish work with the forest of allocno hard registers nodes. */ 831static void 832finish_allocno_hard_regs_nodes_forest (void) 833{ 834 allocno_hard_regs_node_t node, next; 835 836 ira_free (allocno_hard_regs_subnodes); 837 for (node = hard_regs_roots; node != NULL; node = next) 838 { 839 next = node->next; 840 finish_allocno_hard_regs_nodes_tree (node); 841 } 842 ira_free (allocno_hard_regs_nodes); 843 ira_free (allocno_hard_regs_subnode_index); 844 finish_allocno_hard_regs (); 845} 846 847/* Set up left conflict sizes and left conflict subnodes sizes of hard 848 registers subnodes of allocno A. Return TRUE if allocno A is 849 trivially colorable. */ 850static bool 851setup_left_conflict_sizes_p (ira_allocno_t a) 852{ 853 int i, k, nobj, start; 854 int conflict_size, left_conflict_subnodes_size, node_preorder_num; 855 allocno_color_data_t data; 856 HARD_REG_SET profitable_hard_regs; 857 allocno_hard_regs_subnode_t subnodes; 858 allocno_hard_regs_node_t node; 859 HARD_REG_SET node_set; 860 861 nobj = ALLOCNO_NUM_OBJECTS (a); 862 data = ALLOCNO_COLOR_DATA (a); 863 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start; 864 COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs); 865 node = data->hard_regs_node; 866 node_preorder_num = node->preorder_num; 867 COPY_HARD_REG_SET (node_set, node->hard_regs->set); 868 node_check_tick++; 869 for (k = 0; k < nobj; k++) 870 { 871 ira_object_t obj = ALLOCNO_OBJECT (a, k); 872 ira_object_t conflict_obj; 873 ira_object_conflict_iterator oci; 874 875 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 876 { 877 int size; 878 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 879 allocno_hard_regs_node_t conflict_node, temp_node; 880 HARD_REG_SET conflict_node_set; 881 allocno_color_data_t conflict_data; 882 883 conflict_data = ALLOCNO_COLOR_DATA (conflict_a); 884 if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p 885 || ! hard_reg_set_intersect_p (profitable_hard_regs, 886 conflict_data 887 ->profitable_hard_regs)) 888 continue; 889 conflict_node = conflict_data->hard_regs_node; 890 COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set); 891 if (hard_reg_set_subset_p (node_set, conflict_node_set)) 892 temp_node = node; 893 else 894 { 895 ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set)); 896 temp_node = conflict_node; 897 } 898 if (temp_node->check != node_check_tick) 899 { 900 temp_node->check = node_check_tick; 901 temp_node->conflict_size = 0; 902 } 903 size = (ira_reg_class_max_nregs 904 [ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]); 905 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1) 906 /* We will deal with the subwords individually. */ 907 size = 1; 908 temp_node->conflict_size += size; 909 } 910 } 911 for (i = 0; i < data->hard_regs_subnodes_num; i++) 912 { 913 allocno_hard_regs_node_t temp_node; 914 915 temp_node = allocno_hard_regs_nodes[i + node_preorder_num]; 916 ira_assert (temp_node->preorder_num == i + node_preorder_num); 917 subnodes[i].left_conflict_size = (temp_node->check != node_check_tick 918 ? 0 : temp_node->conflict_size); 919 if (hard_reg_set_subset_p (temp_node->hard_regs->set, 920 profitable_hard_regs)) 921 subnodes[i].max_node_impact = temp_node->hard_regs_num; 922 else 923 { 924 HARD_REG_SET temp_set; 925 int j, n, hard_regno; 926 enum reg_class aclass; 927 928 COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set); 929 AND_HARD_REG_SET (temp_set, profitable_hard_regs); 930 aclass = ALLOCNO_CLASS (a); 931 for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--) 932 { 933 hard_regno = ira_class_hard_regs[aclass][j]; 934 if (TEST_HARD_REG_BIT (temp_set, hard_regno)) 935 n++; 936 } 937 subnodes[i].max_node_impact = n; 938 } 939 subnodes[i].left_conflict_subnodes_size = 0; 940 } 941 start = node_preorder_num * allocno_hard_regs_nodes_num; 942 for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--) 943 { 944 int size, parent_i; 945 allocno_hard_regs_node_t parent; 946 947 size = (subnodes[i].left_conflict_subnodes_size 948 + MIN (subnodes[i].max_node_impact 949 - subnodes[i].left_conflict_subnodes_size, 950 subnodes[i].left_conflict_size)); 951 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent; 952 if (parent == NULL) 953 continue; 954 parent_i 955 = allocno_hard_regs_subnode_index[start + parent->preorder_num]; 956 if (parent_i < 0) 957 continue; 958 subnodes[parent_i].left_conflict_subnodes_size += size; 959 } 960 left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size; 961 conflict_size 962 = (left_conflict_subnodes_size 963 + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size, 964 subnodes[0].left_conflict_size)); 965 conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]; 966 data->colorable_p = conflict_size <= data->available_regs_num; 967 return data->colorable_p; 968} 969 970/* Update left conflict sizes of hard registers subnodes of allocno A 971 after removing allocno REMOVED_A with SIZE from the conflict graph. 972 Return TRUE if A is trivially colorable. */ 973static bool 974update_left_conflict_sizes_p (ira_allocno_t a, 975 ira_allocno_t removed_a, int size) 976{ 977 int i, conflict_size, before_conflict_size, diff, start; 978 int node_preorder_num, parent_i; 979 allocno_hard_regs_node_t node, removed_node, parent; 980 allocno_hard_regs_subnode_t subnodes; 981 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); 982 983 ira_assert (! data->colorable_p); 984 node = data->hard_regs_node; 985 node_preorder_num = node->preorder_num; 986 removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node; 987 ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set, 988 node->hard_regs->set) 989 || hard_reg_set_subset_p (node->hard_regs->set, 990 removed_node->hard_regs->set)); 991 start = node_preorder_num * allocno_hard_regs_nodes_num; 992 i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num]; 993 if (i < 0) 994 i = 0; 995 subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start; 996 before_conflict_size 997 = (subnodes[i].left_conflict_subnodes_size 998 + MIN (subnodes[i].max_node_impact 999 - subnodes[i].left_conflict_subnodes_size, 1000 subnodes[i].left_conflict_size)); 1001 subnodes[i].left_conflict_size -= size; 1002 for (;;) 1003 { 1004 conflict_size 1005 = (subnodes[i].left_conflict_subnodes_size 1006 + MIN (subnodes[i].max_node_impact 1007 - subnodes[i].left_conflict_subnodes_size, 1008 subnodes[i].left_conflict_size)); 1009 if ((diff = before_conflict_size - conflict_size) == 0) 1010 break; 1011 ira_assert (conflict_size < before_conflict_size); 1012 parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent; 1013 if (parent == NULL) 1014 break; 1015 parent_i 1016 = allocno_hard_regs_subnode_index[start + parent->preorder_num]; 1017 if (parent_i < 0) 1018 break; 1019 i = parent_i; 1020 before_conflict_size 1021 = (subnodes[i].left_conflict_subnodes_size 1022 + MIN (subnodes[i].max_node_impact 1023 - subnodes[i].left_conflict_subnodes_size, 1024 subnodes[i].left_conflict_size)); 1025 subnodes[i].left_conflict_subnodes_size -= diff; 1026 } 1027 if (i != 0 1028 || (conflict_size 1029 + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)] 1030 > data->available_regs_num)) 1031 return false; 1032 data->colorable_p = true; 1033 return true; 1034} 1035 1036/* Return true if allocno A has empty profitable hard regs. */ 1037static bool 1038empty_profitable_hard_regs (ira_allocno_t a) 1039{ 1040 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); 1041 1042 return hard_reg_set_empty_p (data->profitable_hard_regs); 1043} 1044 1045/* Set up profitable hard registers for each allocno being 1046 colored. */ 1047static void 1048setup_profitable_hard_regs (void) 1049{ 1050 unsigned int i; 1051 int j, k, nobj, hard_regno, nregs, class_size; 1052 ira_allocno_t a; 1053 bitmap_iterator bi; 1054 enum reg_class aclass; 1055 machine_mode mode; 1056 allocno_color_data_t data; 1057 1058 /* Initial set up from allocno classes and explicitly conflicting 1059 hard regs. */ 1060 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 1061 { 1062 a = ira_allocnos[i]; 1063 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS) 1064 continue; 1065 data = ALLOCNO_COLOR_DATA (a); 1066 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL 1067 && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)) 1068 CLEAR_HARD_REG_SET (data->profitable_hard_regs); 1069 else 1070 { 1071 mode = ALLOCNO_MODE (a); 1072 COPY_HARD_REG_SET (data->profitable_hard_regs, 1073 ira_useful_class_mode_regs[aclass][mode]); 1074 nobj = ALLOCNO_NUM_OBJECTS (a); 1075 for (k = 0; k < nobj; k++) 1076 { 1077 ira_object_t obj = ALLOCNO_OBJECT (a, k); 1078 1079 AND_COMPL_HARD_REG_SET (data->profitable_hard_regs, 1080 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 1081 } 1082 } 1083 } 1084 /* Exclude hard regs already assigned for conflicting objects. */ 1085 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi) 1086 { 1087 a = ira_allocnos[i]; 1088 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS 1089 || ! ALLOCNO_ASSIGNED_P (a) 1090 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0) 1091 continue; 1092 mode = ALLOCNO_MODE (a); 1093 nregs = hard_regno_nregs[hard_regno][mode]; 1094 nobj = ALLOCNO_NUM_OBJECTS (a); 1095 for (k = 0; k < nobj; k++) 1096 { 1097 ira_object_t obj = ALLOCNO_OBJECT (a, k); 1098 ira_object_t conflict_obj; 1099 ira_object_conflict_iterator oci; 1100 1101 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 1102 { 1103 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 1104 1105 /* We can process the conflict allocno repeatedly with 1106 the same result. */ 1107 if (nregs == nobj && nregs > 1) 1108 { 1109 int num = OBJECT_SUBWORD (conflict_obj); 1110 1111 if (REG_WORDS_BIG_ENDIAN) 1112 CLEAR_HARD_REG_BIT 1113 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs, 1114 hard_regno + nobj - num - 1); 1115 else 1116 CLEAR_HARD_REG_BIT 1117 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs, 1118 hard_regno + num); 1119 } 1120 else 1121 AND_COMPL_HARD_REG_SET 1122 (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs, 1123 ira_reg_mode_hard_regset[hard_regno][mode]); 1124 } 1125 } 1126 } 1127 /* Exclude too costly hard regs. */ 1128 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 1129 { 1130 int min_cost = INT_MAX; 1131 int *costs; 1132 1133 a = ira_allocnos[i]; 1134 if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS 1135 || empty_profitable_hard_regs (a)) 1136 continue; 1137 data = ALLOCNO_COLOR_DATA (a); 1138 mode = ALLOCNO_MODE (a); 1139 if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL 1140 || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL) 1141 { 1142 class_size = ira_class_hard_regs_num[aclass]; 1143 for (j = 0; j < class_size; j++) 1144 { 1145 hard_regno = ira_class_hard_regs[aclass][j]; 1146 if (! TEST_HARD_REG_BIT (data->profitable_hard_regs, 1147 hard_regno)) 1148 continue; 1149 if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]) 1150 CLEAR_HARD_REG_BIT (data->profitable_hard_regs, 1151 hard_regno); 1152 else if (min_cost > costs[j]) 1153 min_cost = costs[j]; 1154 } 1155 } 1156 else if (ALLOCNO_UPDATED_MEMORY_COST (a) 1157 < ALLOCNO_UPDATED_CLASS_COST (a)) 1158 CLEAR_HARD_REG_SET (data->profitable_hard_regs); 1159 if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost) 1160 ALLOCNO_UPDATED_CLASS_COST (a) = min_cost; 1161 } 1162} 1163 1164 1165 1166/* This page contains functions used to choose hard registers for 1167 allocnos. */ 1168 1169/* Pool for update cost records. */ 1170static alloc_pool update_cost_record_pool; 1171 1172/* Initiate update cost records. */ 1173static void 1174init_update_cost_records (void) 1175{ 1176 update_cost_record_pool 1177 = create_alloc_pool ("update cost records", 1178 sizeof (struct update_cost_record), 100); 1179} 1180 1181/* Return new update cost record with given params. */ 1182static struct update_cost_record * 1183get_update_cost_record (int hard_regno, int divisor, 1184 struct update_cost_record *next) 1185{ 1186 struct update_cost_record *record; 1187 1188 record = (struct update_cost_record *) pool_alloc (update_cost_record_pool); 1189 record->hard_regno = hard_regno; 1190 record->divisor = divisor; 1191 record->next = next; 1192 return record; 1193} 1194 1195/* Free memory for all records in LIST. */ 1196static void 1197free_update_cost_record_list (struct update_cost_record *list) 1198{ 1199 struct update_cost_record *next; 1200 1201 while (list != NULL) 1202 { 1203 next = list->next; 1204 pool_free (update_cost_record_pool, list); 1205 list = next; 1206 } 1207} 1208 1209/* Free memory allocated for all update cost records. */ 1210static void 1211finish_update_cost_records (void) 1212{ 1213 free_alloc_pool (update_cost_record_pool); 1214} 1215 1216/* Array whose element value is TRUE if the corresponding hard 1217 register was already allocated for an allocno. */ 1218static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]; 1219 1220/* Describes one element in a queue of allocnos whose costs need to be 1221 updated. Each allocno in the queue is known to have an allocno 1222 class. */ 1223struct update_cost_queue_elem 1224{ 1225 /* This element is in the queue iff CHECK == update_cost_check. */ 1226 int check; 1227 1228 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path 1229 connecting this allocno to the one being allocated. */ 1230 int divisor; 1231 1232 /* Allocno from which we are chaining costs of connected allocnos. 1233 It is used not go back in graph of allocnos connected by 1234 copies. */ 1235 ira_allocno_t from; 1236 1237 /* The next allocno in the queue, or null if this is the last element. */ 1238 ira_allocno_t next; 1239}; 1240 1241/* The first element in a queue of allocnos whose copy costs need to be 1242 updated. Null if the queue is empty. */ 1243static ira_allocno_t update_cost_queue; 1244 1245/* The last element in the queue described by update_cost_queue. 1246 Not valid if update_cost_queue is null. */ 1247static struct update_cost_queue_elem *update_cost_queue_tail; 1248 1249/* A pool of elements in the queue described by update_cost_queue. 1250 Elements are indexed by ALLOCNO_NUM. */ 1251static struct update_cost_queue_elem *update_cost_queue_elems; 1252 1253/* The current value of update_costs_from_copies call count. */ 1254static int update_cost_check; 1255 1256/* Allocate and initialize data necessary for function 1257 update_costs_from_copies. */ 1258static void 1259initiate_cost_update (void) 1260{ 1261 size_t size; 1262 1263 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem); 1264 update_cost_queue_elems 1265 = (struct update_cost_queue_elem *) ira_allocate (size); 1266 memset (update_cost_queue_elems, 0, size); 1267 update_cost_check = 0; 1268 init_update_cost_records (); 1269} 1270 1271/* Deallocate data used by function update_costs_from_copies. */ 1272static void 1273finish_cost_update (void) 1274{ 1275 ira_free (update_cost_queue_elems); 1276 finish_update_cost_records (); 1277} 1278 1279/* When we traverse allocnos to update hard register costs, the cost 1280 divisor will be multiplied by the following macro value for each 1281 hop from given allocno to directly connected allocnos. */ 1282#define COST_HOP_DIVISOR 4 1283 1284/* Start a new cost-updating pass. */ 1285static void 1286start_update_cost (void) 1287{ 1288 update_cost_check++; 1289 update_cost_queue = NULL; 1290} 1291 1292/* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless 1293 ALLOCNO is already in the queue, or has NO_REGS class. */ 1294static inline void 1295queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor) 1296{ 1297 struct update_cost_queue_elem *elem; 1298 1299 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)]; 1300 if (elem->check != update_cost_check 1301 && ALLOCNO_CLASS (allocno) != NO_REGS) 1302 { 1303 elem->check = update_cost_check; 1304 elem->from = from; 1305 elem->divisor = divisor; 1306 elem->next = NULL; 1307 if (update_cost_queue == NULL) 1308 update_cost_queue = allocno; 1309 else 1310 update_cost_queue_tail->next = allocno; 1311 update_cost_queue_tail = elem; 1312 } 1313} 1314 1315/* Try to remove the first element from update_cost_queue. Return 1316 false if the queue was empty, otherwise make (*ALLOCNO, *FROM, 1317 *DIVISOR) describe the removed element. */ 1318static inline bool 1319get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor) 1320{ 1321 struct update_cost_queue_elem *elem; 1322 1323 if (update_cost_queue == NULL) 1324 return false; 1325 1326 *allocno = update_cost_queue; 1327 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)]; 1328 *from = elem->from; 1329 *divisor = elem->divisor; 1330 update_cost_queue = elem->next; 1331 return true; 1332} 1333 1334/* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return 1335 true if we really modified the cost. */ 1336static bool 1337update_allocno_cost (ira_allocno_t allocno, int hard_regno, int update_cost) 1338{ 1339 int i; 1340 enum reg_class aclass = ALLOCNO_CLASS (allocno); 1341 1342 i = ira_class_hard_reg_index[aclass][hard_regno]; 1343 if (i < 0) 1344 return false; 1345 ira_allocate_and_set_or_copy_costs 1346 (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass, 1347 ALLOCNO_UPDATED_CLASS_COST (allocno), 1348 ALLOCNO_HARD_REG_COSTS (allocno)); 1349 ira_allocate_and_set_or_copy_costs 1350 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno), 1351 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno)); 1352 ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost; 1353 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_cost; 1354 return true; 1355} 1356 1357/* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected 1358 by copies to ALLOCNO to increase chances to remove some copies as 1359 the result of subsequent assignment. Record cost updates if 1360 RECORD_P is true. */ 1361static void 1362update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, 1363 int divisor, bool decr_p, bool record_p) 1364{ 1365 int cost, update_cost; 1366 machine_mode mode; 1367 enum reg_class rclass, aclass; 1368 ira_allocno_t another_allocno, from = NULL; 1369 ira_copy_t cp, next_cp; 1370 1371 rclass = REGNO_REG_CLASS (hard_regno); 1372 do 1373 { 1374 mode = ALLOCNO_MODE (allocno); 1375 ira_init_register_move_cost_if_necessary (mode); 1376 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) 1377 { 1378 if (cp->first == allocno) 1379 { 1380 next_cp = cp->next_first_allocno_copy; 1381 another_allocno = cp->second; 1382 } 1383 else if (cp->second == allocno) 1384 { 1385 next_cp = cp->next_second_allocno_copy; 1386 another_allocno = cp->first; 1387 } 1388 else 1389 gcc_unreachable (); 1390 1391 if (another_allocno == from) 1392 continue; 1393 1394 aclass = ALLOCNO_CLASS (another_allocno); 1395 if (! TEST_HARD_REG_BIT (reg_class_contents[aclass], 1396 hard_regno) 1397 || ALLOCNO_ASSIGNED_P (another_allocno)) 1398 continue; 1399 1400 cost = (cp->second == allocno 1401 ? ira_register_move_cost[mode][rclass][aclass] 1402 : ira_register_move_cost[mode][aclass][rclass]); 1403 if (decr_p) 1404 cost = -cost; 1405 1406 update_cost = cp->freq * cost / divisor; 1407 if (update_cost == 0) 1408 continue; 1409 1410 if (! update_allocno_cost (another_allocno, hard_regno, update_cost)) 1411 continue; 1412 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR); 1413 if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL) 1414 ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records 1415 = get_update_cost_record (hard_regno, divisor, 1416 ALLOCNO_COLOR_DATA (another_allocno) 1417 ->update_cost_records); 1418 } 1419 } 1420 while (get_next_update_cost (&allocno, &from, &divisor)); 1421} 1422 1423/* Decrease preferred ALLOCNO hard register costs and costs of 1424 allocnos connected to ALLOCNO through copy. */ 1425static void 1426update_costs_from_prefs (ira_allocno_t allocno) 1427{ 1428 ira_pref_t pref; 1429 1430 start_update_cost (); 1431 for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref) 1432 update_costs_from_allocno (allocno, pref->hard_regno, 1433 COST_HOP_DIVISOR, true, true); 1434} 1435 1436/* Update (decrease if DECR_P) the cost of allocnos connected to 1437 ALLOCNO through copies to increase chances to remove some copies as 1438 the result of subsequent assignment. ALLOCNO was just assigned to 1439 a hard register. Record cost updates if RECORD_P is true. */ 1440static void 1441update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p) 1442{ 1443 int hard_regno; 1444 1445 hard_regno = ALLOCNO_HARD_REGNO (allocno); 1446 ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS); 1447 start_update_cost (); 1448 update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p); 1449} 1450 1451/* Restore costs of allocnos connected to ALLOCNO by copies as it was 1452 before updating costs of these allocnos from given allocno. This 1453 is a wise thing to do as if given allocno did not get an expected 1454 hard reg, using smaller cost of the hard reg for allocnos connected 1455 by copies to given allocno becomes actually misleading. Free all 1456 update cost records for ALLOCNO as we don't need them anymore. */ 1457static void 1458restore_costs_from_copies (ira_allocno_t allocno) 1459{ 1460 struct update_cost_record *records, *curr; 1461 1462 if (ALLOCNO_COLOR_DATA (allocno) == NULL) 1463 return; 1464 records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records; 1465 start_update_cost (); 1466 for (curr = records; curr != NULL; curr = curr->next) 1467 update_costs_from_allocno (allocno, curr->hard_regno, 1468 curr->divisor, true, false); 1469 free_update_cost_record_list (records); 1470 ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL; 1471} 1472 1473/* This function updates COSTS (decrease if DECR_P) for hard_registers 1474 of ACLASS by conflict costs of the unassigned allocnos 1475 connected by copies with allocnos in update_cost_queue. This 1476 update increases chances to remove some copies. */ 1477static void 1478update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, 1479 bool decr_p) 1480{ 1481 int i, cost, class_size, freq, mult, div, divisor; 1482 int index, hard_regno; 1483 int *conflict_costs; 1484 bool cont_p; 1485 enum reg_class another_aclass; 1486 ira_allocno_t allocno, another_allocno, from; 1487 ira_copy_t cp, next_cp; 1488 1489 while (get_next_update_cost (&allocno, &from, &divisor)) 1490 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) 1491 { 1492 if (cp->first == allocno) 1493 { 1494 next_cp = cp->next_first_allocno_copy; 1495 another_allocno = cp->second; 1496 } 1497 else if (cp->second == allocno) 1498 { 1499 next_cp = cp->next_second_allocno_copy; 1500 another_allocno = cp->first; 1501 } 1502 else 1503 gcc_unreachable (); 1504 1505 if (another_allocno == from) 1506 continue; 1507 1508 another_aclass = ALLOCNO_CLASS (another_allocno); 1509 if (! ira_reg_classes_intersect_p[aclass][another_aclass] 1510 || ALLOCNO_ASSIGNED_P (another_allocno) 1511 || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p) 1512 continue; 1513 class_size = ira_class_hard_regs_num[another_aclass]; 1514 ira_allocate_and_copy_costs 1515 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), 1516 another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); 1517 conflict_costs 1518 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); 1519 if (conflict_costs == NULL) 1520 cont_p = true; 1521 else 1522 { 1523 mult = cp->freq; 1524 freq = ALLOCNO_FREQ (another_allocno); 1525 if (freq == 0) 1526 freq = 1; 1527 div = freq * divisor; 1528 cont_p = false; 1529 for (i = class_size - 1; i >= 0; i--) 1530 { 1531 hard_regno = ira_class_hard_regs[another_aclass][i]; 1532 ira_assert (hard_regno >= 0); 1533 index = ira_class_hard_reg_index[aclass][hard_regno]; 1534 if (index < 0) 1535 continue; 1536 cost = (int) ((unsigned) conflict_costs [i] * mult) / div; 1537 if (cost == 0) 1538 continue; 1539 cont_p = true; 1540 if (decr_p) 1541 cost = -cost; 1542 costs[index] += cost; 1543 } 1544 } 1545 /* Probably 5 hops will be enough. */ 1546 if (cont_p 1547 && divisor <= (COST_HOP_DIVISOR 1548 * COST_HOP_DIVISOR 1549 * COST_HOP_DIVISOR 1550 * COST_HOP_DIVISOR)) 1551 queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR); 1552 } 1553} 1554 1555/* Set up conflicting (through CONFLICT_REGS) for each object of 1556 allocno A and the start allocno profitable regs (through 1557 START_PROFITABLE_REGS). Remember that the start profitable regs 1558 exclude hard regs which can not hold value of mode of allocno A. 1559 This covers mostly cases when multi-register value should be 1560 aligned. */ 1561static inline void 1562get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p, 1563 HARD_REG_SET *conflict_regs, 1564 HARD_REG_SET *start_profitable_regs) 1565{ 1566 int i, nwords; 1567 ira_object_t obj; 1568 1569 nwords = ALLOCNO_NUM_OBJECTS (a); 1570 for (i = 0; i < nwords; i++) 1571 { 1572 obj = ALLOCNO_OBJECT (a, i); 1573 COPY_HARD_REG_SET (conflict_regs[i], 1574 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 1575 } 1576 if (retry_p) 1577 { 1578 COPY_HARD_REG_SET (*start_profitable_regs, 1579 reg_class_contents[ALLOCNO_CLASS (a)]); 1580 AND_COMPL_HARD_REG_SET (*start_profitable_regs, 1581 ira_prohibited_class_mode_regs 1582 [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]); 1583 } 1584 else 1585 COPY_HARD_REG_SET (*start_profitable_regs, 1586 ALLOCNO_COLOR_DATA (a)->profitable_hard_regs); 1587} 1588 1589/* Return true if HARD_REGNO is ok for assigning to allocno A with 1590 PROFITABLE_REGS and whose objects have CONFLICT_REGS. */ 1591static inline bool 1592check_hard_reg_p (ira_allocno_t a, int hard_regno, 1593 HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs) 1594{ 1595 int j, nwords, nregs; 1596 enum reg_class aclass; 1597 machine_mode mode; 1598 1599 aclass = ALLOCNO_CLASS (a); 1600 mode = ALLOCNO_MODE (a); 1601 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode], 1602 hard_regno)) 1603 return false; 1604 /* Checking only profitable hard regs. */ 1605 if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno)) 1606 return false; 1607 nregs = hard_regno_nregs[hard_regno][mode]; 1608 nwords = ALLOCNO_NUM_OBJECTS (a); 1609 for (j = 0; j < nregs; j++) 1610 { 1611 int k; 1612 int set_to_test_start = 0, set_to_test_end = nwords; 1613 1614 if (nregs == nwords) 1615 { 1616 if (REG_WORDS_BIG_ENDIAN) 1617 set_to_test_start = nwords - j - 1; 1618 else 1619 set_to_test_start = j; 1620 set_to_test_end = set_to_test_start + 1; 1621 } 1622 for (k = set_to_test_start; k < set_to_test_end; k++) 1623 if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j)) 1624 break; 1625 if (k != set_to_test_end) 1626 break; 1627 } 1628 return j == nregs; 1629} 1630 1631/* Return number of registers needed to be saved and restored at 1632 function prologue/epilogue if we allocate HARD_REGNO to hold value 1633 of MODE. */ 1634static int 1635calculate_saved_nregs (int hard_regno, machine_mode mode) 1636{ 1637 int i; 1638 int nregs = 0; 1639 1640 ira_assert (hard_regno >= 0); 1641 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--) 1642 if (!allocated_hardreg_p[hard_regno + i] 1643 && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i) 1644 && !LOCAL_REGNO (hard_regno + i)) 1645 nregs++; 1646 return nregs; 1647} 1648 1649/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means 1650 that the function called from function 1651 `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In 1652 this case some allocno data are not defined or updated and we 1653 should not touch these data. The function returns true if we 1654 managed to assign a hard register to the allocno. 1655 1656 To assign a hard register, first of all we calculate all conflict 1657 hard registers which can come from conflicting allocnos with 1658 already assigned hard registers. After that we find first free 1659 hard register with the minimal cost. During hard register cost 1660 calculation we take conflict hard register costs into account to 1661 give a chance for conflicting allocnos to get a better hard 1662 register in the future. 1663 1664 If the best hard register cost is bigger than cost of memory usage 1665 for the allocno, we don't assign a hard register to given allocno 1666 at all. 1667 1668 If we assign a hard register to the allocno, we update costs of the 1669 hard register for allocnos connected by copies to improve a chance 1670 to coalesce insns represented by the copies when we assign hard 1671 registers to the allocnos connected by the copies. */ 1672static bool 1673assign_hard_reg (ira_allocno_t a, bool retry_p) 1674{ 1675 HARD_REG_SET conflicting_regs[2], profitable_hard_regs; 1676 int i, j, hard_regno, best_hard_regno, class_size; 1677 int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word; 1678 int *a_costs; 1679 enum reg_class aclass; 1680 machine_mode mode; 1681 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER]; 1682 int saved_nregs; 1683 enum reg_class rclass; 1684 int add_cost; 1685#ifdef STACK_REGS 1686 bool no_stack_reg_p; 1687#endif 1688 1689 ira_assert (! ALLOCNO_ASSIGNED_P (a)); 1690 get_conflict_and_start_profitable_regs (a, retry_p, 1691 conflicting_regs, 1692 &profitable_hard_regs); 1693 aclass = ALLOCNO_CLASS (a); 1694 class_size = ira_class_hard_regs_num[aclass]; 1695 best_hard_regno = -1; 1696 memset (full_costs, 0, sizeof (int) * class_size); 1697 mem_cost = 0; 1698 memset (costs, 0, sizeof (int) * class_size); 1699 memset (full_costs, 0, sizeof (int) * class_size); 1700#ifdef STACK_REGS 1701 no_stack_reg_p = false; 1702#endif 1703 if (! retry_p) 1704 start_update_cost (); 1705 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a); 1706 1707 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), 1708 aclass, ALLOCNO_HARD_REG_COSTS (a)); 1709 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a); 1710#ifdef STACK_REGS 1711 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a); 1712#endif 1713 cost = ALLOCNO_UPDATED_CLASS_COST (a); 1714 for (i = 0; i < class_size; i++) 1715 if (a_costs != NULL) 1716 { 1717 costs[i] += a_costs[i]; 1718 full_costs[i] += a_costs[i]; 1719 } 1720 else 1721 { 1722 costs[i] += cost; 1723 full_costs[i] += cost; 1724 } 1725 nwords = ALLOCNO_NUM_OBJECTS (a); 1726 curr_allocno_process++; 1727 for (word = 0; word < nwords; word++) 1728 { 1729 ira_object_t conflict_obj; 1730 ira_object_t obj = ALLOCNO_OBJECT (a, word); 1731 ira_object_conflict_iterator oci; 1732 1733 /* Take preferences of conflicting allocnos into account. */ 1734 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 1735 { 1736 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 1737 enum reg_class conflict_aclass; 1738 allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a); 1739 1740 /* Reload can give another class so we need to check all 1741 allocnos. */ 1742 if (!retry_p 1743 && (!bitmap_bit_p (consideration_allocno_bitmap, 1744 ALLOCNO_NUM (conflict_a)) 1745 || ((!ALLOCNO_ASSIGNED_P (conflict_a) 1746 || ALLOCNO_HARD_REGNO (conflict_a) < 0) 1747 && !(hard_reg_set_intersect_p 1748 (profitable_hard_regs, 1749 ALLOCNO_COLOR_DATA 1750 (conflict_a)->profitable_hard_regs))))) 1751 continue; 1752 conflict_aclass = ALLOCNO_CLASS (conflict_a); 1753 ira_assert (ira_reg_classes_intersect_p 1754 [aclass][conflict_aclass]); 1755 if (ALLOCNO_ASSIGNED_P (conflict_a)) 1756 { 1757 hard_regno = ALLOCNO_HARD_REGNO (conflict_a); 1758 if (hard_regno >= 0 1759 && (ira_hard_reg_set_intersection_p 1760 (hard_regno, ALLOCNO_MODE (conflict_a), 1761 reg_class_contents[aclass]))) 1762 { 1763 int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a); 1764 int conflict_nregs; 1765 1766 mode = ALLOCNO_MODE (conflict_a); 1767 conflict_nregs = hard_regno_nregs[hard_regno][mode]; 1768 if (conflict_nregs == n_objects && conflict_nregs > 1) 1769 { 1770 int num = OBJECT_SUBWORD (conflict_obj); 1771 1772 if (REG_WORDS_BIG_ENDIAN) 1773 SET_HARD_REG_BIT (conflicting_regs[word], 1774 hard_regno + n_objects - num - 1); 1775 else 1776 SET_HARD_REG_BIT (conflicting_regs[word], 1777 hard_regno + num); 1778 } 1779 else 1780 IOR_HARD_REG_SET 1781 (conflicting_regs[word], 1782 ira_reg_mode_hard_regset[hard_regno][mode]); 1783 if (hard_reg_set_subset_p (profitable_hard_regs, 1784 conflicting_regs[word])) 1785 goto fail; 1786 } 1787 } 1788 else if (! retry_p 1789 && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p 1790 /* Don't process the conflict allocno twice. */ 1791 && (ALLOCNO_COLOR_DATA (conflict_a)->last_process 1792 != curr_allocno_process)) 1793 { 1794 int k, *conflict_costs; 1795 1796 ALLOCNO_COLOR_DATA (conflict_a)->last_process 1797 = curr_allocno_process; 1798 ira_allocate_and_copy_costs 1799 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a), 1800 conflict_aclass, 1801 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a)); 1802 conflict_costs 1803 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a); 1804 if (conflict_costs != NULL) 1805 for (j = class_size - 1; j >= 0; j--) 1806 { 1807 hard_regno = ira_class_hard_regs[aclass][j]; 1808 ira_assert (hard_regno >= 0); 1809 k = ira_class_hard_reg_index[conflict_aclass][hard_regno]; 1810 if (k < 0 1811 /* If HARD_REGNO is not available for CONFLICT_A, 1812 the conflict would be ignored, since HARD_REGNO 1813 will never be assigned to CONFLICT_A. */ 1814 || !TEST_HARD_REG_BIT (data->profitable_hard_regs, 1815 hard_regno)) 1816 continue; 1817 full_costs[j] -= conflict_costs[k]; 1818 } 1819 queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR); 1820 1821 } 1822 } 1823 } 1824 if (! retry_p) 1825 /* Take into account preferences of allocnos connected by copies to 1826 the conflict allocnos. */ 1827 update_conflict_hard_regno_costs (full_costs, aclass, true); 1828 1829 /* Take preferences of allocnos connected by copies into 1830 account. */ 1831 if (! retry_p) 1832 { 1833 start_update_cost (); 1834 queue_update_cost (a, NULL, COST_HOP_DIVISOR); 1835 update_conflict_hard_regno_costs (full_costs, aclass, false); 1836 } 1837 min_cost = min_full_cost = INT_MAX; 1838 /* We don't care about giving callee saved registers to allocnos no 1839 living through calls because call clobbered registers are 1840 allocated first (it is usual practice to put them first in 1841 REG_ALLOC_ORDER). */ 1842 mode = ALLOCNO_MODE (a); 1843 for (i = 0; i < class_size; i++) 1844 { 1845 hard_regno = ira_class_hard_regs[aclass][i]; 1846#ifdef STACK_REGS 1847 if (no_stack_reg_p 1848 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG) 1849 continue; 1850#endif 1851 if (! check_hard_reg_p (a, hard_regno, 1852 conflicting_regs, profitable_hard_regs)) 1853 continue; 1854 cost = costs[i]; 1855 full_cost = full_costs[i]; 1856 if (!HONOR_REG_ALLOC_ORDER) 1857 { 1858 if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0) 1859 /* We need to save/restore the hard register in 1860 epilogue/prologue. Therefore we increase the cost. */ 1861 { 1862 rclass = REGNO_REG_CLASS (hard_regno); 1863 add_cost = ((ira_memory_move_cost[mode][rclass][0] 1864 + ira_memory_move_cost[mode][rclass][1]) 1865 * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1); 1866 cost += add_cost; 1867 full_cost += add_cost; 1868 } 1869 } 1870 if (min_cost > cost) 1871 min_cost = cost; 1872 if (min_full_cost > full_cost) 1873 { 1874 min_full_cost = full_cost; 1875 best_hard_regno = hard_regno; 1876 ira_assert (hard_regno >= 0); 1877 } 1878 } 1879 if (min_full_cost > mem_cost) 1880 { 1881 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 1882 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ", 1883 mem_cost, min_full_cost); 1884 best_hard_regno = -1; 1885 } 1886 fail: 1887 if (best_hard_regno >= 0) 1888 { 1889 for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--) 1890 allocated_hardreg_p[best_hard_regno + i] = true; 1891 } 1892 if (! retry_p) 1893 restore_costs_from_copies (a); 1894 ALLOCNO_HARD_REGNO (a) = best_hard_regno; 1895 ALLOCNO_ASSIGNED_P (a) = true; 1896 if (best_hard_regno >= 0) 1897 update_costs_from_copies (a, true, ! retry_p); 1898 ira_assert (ALLOCNO_CLASS (a) == aclass); 1899 /* We don't need updated costs anymore. */ 1900 ira_free_allocno_updated_costs (a); 1901 return best_hard_regno >= 0; 1902} 1903 1904 1905 1906/* An array used to sort copies. */ 1907static ira_copy_t *sorted_copies; 1908 1909/* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is 1910 used to find a conflict for new allocnos or allocnos with the 1911 different allocno classes. */ 1912static bool 1913allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2) 1914{ 1915 rtx reg1, reg2; 1916 int i, j; 1917 int n1 = ALLOCNO_NUM_OBJECTS (a1); 1918 int n2 = ALLOCNO_NUM_OBJECTS (a2); 1919 1920 if (a1 == a2) 1921 return false; 1922 reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)]; 1923 reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)]; 1924 if (reg1 != NULL && reg2 != NULL 1925 && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2)) 1926 return false; 1927 1928 for (i = 0; i < n1; i++) 1929 { 1930 ira_object_t c1 = ALLOCNO_OBJECT (a1, i); 1931 1932 for (j = 0; j < n2; j++) 1933 { 1934 ira_object_t c2 = ALLOCNO_OBJECT (a2, j); 1935 1936 if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1), 1937 OBJECT_LIVE_RANGES (c2))) 1938 return true; 1939 } 1940 } 1941 return false; 1942} 1943 1944/* The function is used to sort copies according to their execution 1945 frequencies. */ 1946static int 1947copy_freq_compare_func (const void *v1p, const void *v2p) 1948{ 1949 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p; 1950 int pri1, pri2; 1951 1952 pri1 = cp1->freq; 1953 pri2 = cp2->freq; 1954 if (pri2 - pri1) 1955 return pri2 - pri1; 1956 1957 /* If frequencies are equal, sort by copies, so that the results of 1958 qsort leave nothing to chance. */ 1959 return cp1->num - cp2->num; 1960} 1961 1962 1963 1964/* Return true if any allocno from thread of A1 conflicts with any 1965 allocno from thread A2. */ 1966static bool 1967allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2) 1968{ 1969 ira_allocno_t a, conflict_a; 1970 1971 for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;; 1972 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) 1973 { 1974 for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;; 1975 conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno) 1976 { 1977 if (allocnos_conflict_by_live_ranges_p (a, conflict_a)) 1978 return true; 1979 if (conflict_a == a1) 1980 break; 1981 } 1982 if (a == a2) 1983 break; 1984 } 1985 return false; 1986} 1987 1988/* Merge two threads given correspondingly by their first allocnos T1 1989 and T2 (more accurately merging T2 into T1). */ 1990static void 1991merge_threads (ira_allocno_t t1, ira_allocno_t t2) 1992{ 1993 ira_allocno_t a, next, last; 1994 1995 gcc_assert (t1 != t2 1996 && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1 1997 && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2); 1998 for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;; 1999 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) 2000 { 2001 ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1; 2002 if (a == t2) 2003 break; 2004 last = a; 2005 } 2006 next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno; 2007 ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2; 2008 ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next; 2009 ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq; 2010} 2011 2012/* Create threads by processing CP_NUM copies from sorted copies. We 2013 process the most expensive copies first. */ 2014static void 2015form_threads_from_copies (int cp_num) 2016{ 2017 ira_allocno_t a, thread1, thread2; 2018 ira_copy_t cp; 2019 int i, n; 2020 2021 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); 2022 /* Form threads processing copies, most frequently executed 2023 first. */ 2024 for (; cp_num != 0;) 2025 { 2026 for (i = 0; i < cp_num; i++) 2027 { 2028 cp = sorted_copies[i]; 2029 thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno; 2030 thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno; 2031 if (thread1 == thread2) 2032 continue; 2033 if (! allocno_thread_conflict_p (thread1, thread2)) 2034 { 2035 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2036 fprintf 2037 (ira_dump_file, 2038 " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n", 2039 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), 2040 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), 2041 cp->freq); 2042 merge_threads (thread1, thread2); 2043 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2044 { 2045 thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno; 2046 fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)", 2047 ALLOCNO_COLOR_DATA (thread1)->thread_freq, 2048 ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1), 2049 ALLOCNO_FREQ (thread1)); 2050 for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno; 2051 a != thread1; 2052 a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno) 2053 fprintf (ira_dump_file, " a%dr%d(%d)", 2054 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), 2055 ALLOCNO_FREQ (a)); 2056 fprintf (ira_dump_file, "\n"); 2057 } 2058 i++; 2059 break; 2060 } 2061 } 2062 /* Collect the rest of copies. */ 2063 for (n = 0; i < cp_num; i++) 2064 { 2065 cp = sorted_copies[i]; 2066 if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno 2067 != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno) 2068 sorted_copies[n++] = cp; 2069 } 2070 cp_num = n; 2071 } 2072} 2073 2074/* Create threads by processing copies of all alocnos from BUCKET. We 2075 process the most expensive copies first. */ 2076static void 2077form_threads_from_bucket (ira_allocno_t bucket) 2078{ 2079 ira_allocno_t a; 2080 ira_copy_t cp, next_cp; 2081 int cp_num = 0; 2082 2083 for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) 2084 { 2085 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 2086 { 2087 if (cp->first == a) 2088 { 2089 next_cp = cp->next_first_allocno_copy; 2090 sorted_copies[cp_num++] = cp; 2091 } 2092 else if (cp->second == a) 2093 next_cp = cp->next_second_allocno_copy; 2094 else 2095 gcc_unreachable (); 2096 } 2097 } 2098 form_threads_from_copies (cp_num); 2099} 2100 2101/* Create threads by processing copies of colorable allocno A. We 2102 process most expensive copies first. */ 2103static void 2104form_threads_from_colorable_allocno (ira_allocno_t a) 2105{ 2106 ira_allocno_t another_a; 2107 ira_copy_t cp, next_cp; 2108 int cp_num = 0; 2109 2110 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 2111 { 2112 if (cp->first == a) 2113 { 2114 next_cp = cp->next_first_allocno_copy; 2115 another_a = cp->second; 2116 } 2117 else if (cp->second == a) 2118 { 2119 next_cp = cp->next_second_allocno_copy; 2120 another_a = cp->first; 2121 } 2122 else 2123 gcc_unreachable (); 2124 if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p 2125 && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p) 2126 || ALLOCNO_COLOR_DATA (another_a)->colorable_p) 2127 sorted_copies[cp_num++] = cp; 2128 } 2129 form_threads_from_copies (cp_num); 2130} 2131 2132/* Form initial threads which contain only one allocno. */ 2133static void 2134init_allocno_threads (void) 2135{ 2136 ira_allocno_t a; 2137 unsigned int j; 2138 bitmap_iterator bi; 2139 2140 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) 2141 { 2142 a = ira_allocnos[j]; 2143 /* Set up initial thread data: */ 2144 ALLOCNO_COLOR_DATA (a)->first_thread_allocno 2145 = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a; 2146 ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a); 2147 } 2148} 2149 2150 2151 2152/* This page contains the allocator based on the Chaitin-Briggs algorithm. */ 2153 2154/* Bucket of allocnos that can colored currently without spilling. */ 2155static ira_allocno_t colorable_allocno_bucket; 2156 2157/* Bucket of allocnos that might be not colored currently without 2158 spilling. */ 2159static ira_allocno_t uncolorable_allocno_bucket; 2160 2161/* The current number of allocnos in the uncolorable_bucket. */ 2162static int uncolorable_allocnos_num; 2163 2164/* Return the current spill priority of allocno A. The less the 2165 number, the more preferable the allocno for spilling. */ 2166static inline int 2167allocno_spill_priority (ira_allocno_t a) 2168{ 2169 allocno_color_data_t data = ALLOCNO_COLOR_DATA (a); 2170 2171 return (data->temp 2172 / (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) 2173 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)] 2174 + 1)); 2175} 2176 2177/* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket 2178 before the call. */ 2179static void 2180add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr) 2181{ 2182 ira_allocno_t first_a; 2183 allocno_color_data_t data; 2184 2185 if (bucket_ptr == &uncolorable_allocno_bucket 2186 && ALLOCNO_CLASS (a) != NO_REGS) 2187 { 2188 uncolorable_allocnos_num++; 2189 ira_assert (uncolorable_allocnos_num > 0); 2190 } 2191 first_a = *bucket_ptr; 2192 data = ALLOCNO_COLOR_DATA (a); 2193 data->next_bucket_allocno = first_a; 2194 data->prev_bucket_allocno = NULL; 2195 if (first_a != NULL) 2196 ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a; 2197 *bucket_ptr = a; 2198} 2199 2200/* Compare two allocnos to define which allocno should be pushed first 2201 into the coloring stack. If the return is a negative number, the 2202 allocno given by the first parameter will be pushed first. In this 2203 case such allocno has less priority than the second one and the 2204 hard register will be assigned to it after assignment to the second 2205 one. As the result of such assignment order, the second allocno 2206 has a better chance to get the best hard register. */ 2207static int 2208bucket_allocno_compare_func (const void *v1p, const void *v2p) 2209{ 2210 ira_allocno_t a1 = *(const ira_allocno_t *) v1p; 2211 ira_allocno_t a2 = *(const ira_allocno_t *) v2p; 2212 int diff, freq1, freq2, a1_num, a2_num; 2213 ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno; 2214 ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno; 2215 int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2); 2216 2217 freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq; 2218 freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq; 2219 if ((diff = freq1 - freq2) != 0) 2220 return diff; 2221 2222 if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0) 2223 return diff; 2224 2225 /* Push pseudos requiring less hard registers first. It means that 2226 we will assign pseudos requiring more hard registers first 2227 avoiding creation small holes in free hard register file into 2228 which the pseudos requiring more hard registers can not fit. */ 2229 if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)] 2230 - ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0) 2231 return diff; 2232 2233 freq1 = ALLOCNO_FREQ (a1); 2234 freq2 = ALLOCNO_FREQ (a2); 2235 if ((diff = freq1 - freq2) != 0) 2236 return diff; 2237 2238 a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num; 2239 a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num; 2240 if ((diff = a2_num - a1_num) != 0) 2241 return diff; 2242 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1); 2243} 2244 2245/* Sort bucket *BUCKET_PTR and return the result through 2246 BUCKET_PTR. */ 2247static void 2248sort_bucket (ira_allocno_t *bucket_ptr, 2249 int (*compare_func) (const void *, const void *)) 2250{ 2251 ira_allocno_t a, head; 2252 int n; 2253 2254 for (n = 0, a = *bucket_ptr; 2255 a != NULL; 2256 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) 2257 sorted_allocnos[n++] = a; 2258 if (n <= 1) 2259 return; 2260 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func); 2261 head = NULL; 2262 for (n--; n >= 0; n--) 2263 { 2264 a = sorted_allocnos[n]; 2265 ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head; 2266 ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL; 2267 if (head != NULL) 2268 ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a; 2269 head = a; 2270 } 2271 *bucket_ptr = head; 2272} 2273 2274/* Add ALLOCNO to colorable bucket maintaining the order according 2275 their priority. ALLOCNO should be not in a bucket before the 2276 call. */ 2277static void 2278add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno) 2279{ 2280 ira_allocno_t before, after; 2281 2282 form_threads_from_colorable_allocno (allocno); 2283 for (before = colorable_allocno_bucket, after = NULL; 2284 before != NULL; 2285 after = before, 2286 before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno) 2287 if (bucket_allocno_compare_func (&allocno, &before) < 0) 2288 break; 2289 ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before; 2290 ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after; 2291 if (after == NULL) 2292 colorable_allocno_bucket = allocno; 2293 else 2294 ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno; 2295 if (before != NULL) 2296 ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno; 2297} 2298 2299/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before 2300 the call. */ 2301static void 2302delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) 2303{ 2304 ira_allocno_t prev_allocno, next_allocno; 2305 2306 if (bucket_ptr == &uncolorable_allocno_bucket 2307 && ALLOCNO_CLASS (allocno) != NO_REGS) 2308 { 2309 uncolorable_allocnos_num--; 2310 ira_assert (uncolorable_allocnos_num >= 0); 2311 } 2312 prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno; 2313 next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno; 2314 if (prev_allocno != NULL) 2315 ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno; 2316 else 2317 { 2318 ira_assert (*bucket_ptr == allocno); 2319 *bucket_ptr = next_allocno; 2320 } 2321 if (next_allocno != NULL) 2322 ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno; 2323} 2324 2325/* Put allocno A onto the coloring stack without removing it from its 2326 bucket. Pushing allocno to the coloring stack can result in moving 2327 conflicting allocnos from the uncolorable bucket to the colorable 2328 one. */ 2329static void 2330push_allocno_to_stack (ira_allocno_t a) 2331{ 2332 enum reg_class aclass; 2333 allocno_color_data_t data, conflict_data; 2334 int size, i, n = ALLOCNO_NUM_OBJECTS (a); 2335 2336 data = ALLOCNO_COLOR_DATA (a); 2337 data->in_graph_p = false; 2338 allocno_stack_vec.safe_push (a); 2339 aclass = ALLOCNO_CLASS (a); 2340 if (aclass == NO_REGS) 2341 return; 2342 size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)]; 2343 if (n > 1) 2344 { 2345 /* We will deal with the subwords individually. */ 2346 gcc_assert (size == ALLOCNO_NUM_OBJECTS (a)); 2347 size = 1; 2348 } 2349 for (i = 0; i < n; i++) 2350 { 2351 ira_object_t obj = ALLOCNO_OBJECT (a, i); 2352 ira_object_t conflict_obj; 2353 ira_object_conflict_iterator oci; 2354 2355 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 2356 { 2357 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 2358 2359 conflict_data = ALLOCNO_COLOR_DATA (conflict_a); 2360 if (conflict_data->colorable_p 2361 || ! conflict_data->in_graph_p 2362 || ALLOCNO_ASSIGNED_P (conflict_a) 2363 || !(hard_reg_set_intersect_p 2364 (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs, 2365 conflict_data->profitable_hard_regs))) 2366 continue; 2367 ira_assert (bitmap_bit_p (coloring_allocno_bitmap, 2368 ALLOCNO_NUM (conflict_a))); 2369 if (update_left_conflict_sizes_p (conflict_a, a, size)) 2370 { 2371 delete_allocno_from_bucket 2372 (conflict_a, &uncolorable_allocno_bucket); 2373 add_allocno_to_ordered_colorable_bucket (conflict_a); 2374 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 2375 { 2376 fprintf (ira_dump_file, " Making"); 2377 ira_print_expanded_allocno (conflict_a); 2378 fprintf (ira_dump_file, " colorable\n"); 2379 } 2380 } 2381 2382 } 2383 } 2384} 2385 2386/* Put ALLOCNO onto the coloring stack and remove it from its bucket. 2387 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */ 2388static void 2389remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p) 2390{ 2391 if (colorable_p) 2392 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket); 2393 else 2394 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket); 2395 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2396 { 2397 fprintf (ira_dump_file, " Pushing"); 2398 ira_print_expanded_allocno (allocno); 2399 if (colorable_p) 2400 fprintf (ira_dump_file, "(cost %d)\n", 2401 ALLOCNO_COLOR_DATA (allocno)->temp); 2402 else 2403 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n", 2404 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "", 2405 allocno_spill_priority (allocno), 2406 ALLOCNO_COLOR_DATA (allocno)->temp); 2407 } 2408 if (! colorable_p) 2409 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true; 2410 push_allocno_to_stack (allocno); 2411} 2412 2413/* Put all allocnos from colorable bucket onto the coloring stack. */ 2414static void 2415push_only_colorable (void) 2416{ 2417 form_threads_from_bucket (colorable_allocno_bucket); 2418 sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func); 2419 for (;colorable_allocno_bucket != NULL;) 2420 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true); 2421} 2422 2423/* Return the frequency of exit edges (if EXIT_P) or entry from/to the 2424 loop given by its LOOP_NODE. */ 2425int 2426ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) 2427{ 2428 int freq, i; 2429 edge_iterator ei; 2430 edge e; 2431 vec<edge> edges; 2432 2433 ira_assert (current_loops != NULL && loop_node->loop != NULL 2434 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER)); 2435 freq = 0; 2436 if (! exit_p) 2437 { 2438 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds) 2439 if (e->src != loop_node->loop->latch 2440 && (regno < 0 2441 || (bitmap_bit_p (df_get_live_out (e->src), regno) 2442 && bitmap_bit_p (df_get_live_in (e->dest), regno)))) 2443 freq += EDGE_FREQUENCY (e); 2444 } 2445 else 2446 { 2447 edges = get_loop_exit_edges (loop_node->loop); 2448 FOR_EACH_VEC_ELT (edges, i, e) 2449 if (regno < 0 2450 || (bitmap_bit_p (df_get_live_out (e->src), regno) 2451 && bitmap_bit_p (df_get_live_in (e->dest), regno))) 2452 freq += EDGE_FREQUENCY (e); 2453 edges.release (); 2454 } 2455 2456 return REG_FREQ_FROM_EDGE_FREQ (freq); 2457} 2458 2459/* Calculate and return the cost of putting allocno A into memory. */ 2460static int 2461calculate_allocno_spill_cost (ira_allocno_t a) 2462{ 2463 int regno, cost; 2464 machine_mode mode; 2465 enum reg_class rclass; 2466 ira_allocno_t parent_allocno; 2467 ira_loop_tree_node_t parent_node, loop_node; 2468 2469 regno = ALLOCNO_REGNO (a); 2470 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a); 2471 if (ALLOCNO_CAP (a) != NULL) 2472 return cost; 2473 loop_node = ALLOCNO_LOOP_TREE_NODE (a); 2474 if ((parent_node = loop_node->parent) == NULL) 2475 return cost; 2476 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL) 2477 return cost; 2478 mode = ALLOCNO_MODE (a); 2479 rclass = ALLOCNO_CLASS (a); 2480 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0) 2481 cost -= (ira_memory_move_cost[mode][rclass][0] 2482 * ira_loop_edge_freq (loop_node, regno, true) 2483 + ira_memory_move_cost[mode][rclass][1] 2484 * ira_loop_edge_freq (loop_node, regno, false)); 2485 else 2486 { 2487 ira_init_register_move_cost_if_necessary (mode); 2488 cost += ((ira_memory_move_cost[mode][rclass][1] 2489 * ira_loop_edge_freq (loop_node, regno, true) 2490 + ira_memory_move_cost[mode][rclass][0] 2491 * ira_loop_edge_freq (loop_node, regno, false)) 2492 - (ira_register_move_cost[mode][rclass][rclass] 2493 * (ira_loop_edge_freq (loop_node, regno, false) 2494 + ira_loop_edge_freq (loop_node, regno, true)))); 2495 } 2496 return cost; 2497} 2498 2499/* Used for sorting allocnos for spilling. */ 2500static inline int 2501allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2) 2502{ 2503 int pri1, pri2, diff; 2504 2505 if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2)) 2506 return 1; 2507 if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1)) 2508 return -1; 2509 pri1 = allocno_spill_priority (a1); 2510 pri2 = allocno_spill_priority (a2); 2511 if ((diff = pri1 - pri2) != 0) 2512 return diff; 2513 if ((diff 2514 = ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0) 2515 return diff; 2516 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); 2517} 2518 2519/* Used for sorting allocnos for spilling. */ 2520static int 2521allocno_spill_sort_compare (const void *v1p, const void *v2p) 2522{ 2523 ira_allocno_t p1 = *(const ira_allocno_t *) v1p; 2524 ira_allocno_t p2 = *(const ira_allocno_t *) v2p; 2525 2526 return allocno_spill_priority_compare (p1, p2); 2527} 2528 2529/* Push allocnos to the coloring stack. The order of allocnos in the 2530 stack defines the order for the subsequent coloring. */ 2531static void 2532push_allocnos_to_stack (void) 2533{ 2534 ira_allocno_t a; 2535 int cost; 2536 2537 /* Calculate uncolorable allocno spill costs. */ 2538 for (a = uncolorable_allocno_bucket; 2539 a != NULL; 2540 a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno) 2541 if (ALLOCNO_CLASS (a) != NO_REGS) 2542 { 2543 cost = calculate_allocno_spill_cost (a); 2544 /* ??? Remove cost of copies between the coalesced 2545 allocnos. */ 2546 ALLOCNO_COLOR_DATA (a)->temp = cost; 2547 } 2548 sort_bucket (&uncolorable_allocno_bucket, allocno_spill_sort_compare); 2549 for (;;) 2550 { 2551 push_only_colorable (); 2552 a = uncolorable_allocno_bucket; 2553 if (a == NULL) 2554 break; 2555 remove_allocno_from_bucket_and_push (a, false); 2556 } 2557 ira_assert (colorable_allocno_bucket == NULL 2558 && uncolorable_allocno_bucket == NULL); 2559 ira_assert (uncolorable_allocnos_num == 0); 2560} 2561 2562/* Pop the coloring stack and assign hard registers to the popped 2563 allocnos. */ 2564static void 2565pop_allocnos_from_stack (void) 2566{ 2567 ira_allocno_t allocno; 2568 enum reg_class aclass; 2569 2570 for (;allocno_stack_vec.length () != 0;) 2571 { 2572 allocno = allocno_stack_vec.pop (); 2573 aclass = ALLOCNO_CLASS (allocno); 2574 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2575 { 2576 fprintf (ira_dump_file, " Popping"); 2577 ira_print_expanded_allocno (allocno); 2578 fprintf (ira_dump_file, " -- "); 2579 } 2580 if (aclass == NO_REGS) 2581 { 2582 ALLOCNO_HARD_REGNO (allocno) = -1; 2583 ALLOCNO_ASSIGNED_P (allocno) = true; 2584 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL); 2585 ira_assert 2586 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL); 2587 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2588 fprintf (ira_dump_file, "assign memory\n"); 2589 } 2590 else if (assign_hard_reg (allocno, false)) 2591 { 2592 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2593 fprintf (ira_dump_file, "assign reg %d\n", 2594 ALLOCNO_HARD_REGNO (allocno)); 2595 } 2596 else if (ALLOCNO_ASSIGNED_P (allocno)) 2597 { 2598 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2599 fprintf (ira_dump_file, "spill%s\n", 2600 ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p 2601 ? "" : "!"); 2602 } 2603 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true; 2604 } 2605} 2606 2607/* Set up number of available hard registers for allocno A. */ 2608static void 2609setup_allocno_available_regs_num (ira_allocno_t a) 2610{ 2611 int i, n, hard_regno, hard_regs_num, nwords; 2612 enum reg_class aclass; 2613 allocno_color_data_t data; 2614 2615 aclass = ALLOCNO_CLASS (a); 2616 data = ALLOCNO_COLOR_DATA (a); 2617 data->available_regs_num = 0; 2618 if (aclass == NO_REGS) 2619 return; 2620 hard_regs_num = ira_class_hard_regs_num[aclass]; 2621 nwords = ALLOCNO_NUM_OBJECTS (a); 2622 for (n = 0, i = hard_regs_num - 1; i >= 0; i--) 2623 { 2624 hard_regno = ira_class_hard_regs[aclass][i]; 2625 /* Checking only profitable hard regs. */ 2626 if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno)) 2627 n++; 2628 } 2629 data->available_regs_num = n; 2630 if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL) 2631 return; 2632 fprintf 2633 (ira_dump_file, 2634 " Allocno a%dr%d of %s(%d) has %d avail. regs ", 2635 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), 2636 reg_class_names[aclass], ira_class_hard_regs_num[aclass], n); 2637 print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false); 2638 fprintf (ira_dump_file, ", %snode: ", 2639 hard_reg_set_equal_p (data->profitable_hard_regs, 2640 data->hard_regs_node->hard_regs->set) 2641 ? "" : "^"); 2642 print_hard_reg_set (ira_dump_file, 2643 data->hard_regs_node->hard_regs->set, false); 2644 for (i = 0; i < nwords; i++) 2645 { 2646 ira_object_t obj = ALLOCNO_OBJECT (a, i); 2647 2648 if (nwords != 1) 2649 { 2650 if (i != 0) 2651 fprintf (ira_dump_file, ", "); 2652 fprintf (ira_dump_file, " obj %d", i); 2653 } 2654 fprintf (ira_dump_file, " (confl regs = "); 2655 print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 2656 false); 2657 fprintf (ira_dump_file, ")"); 2658 } 2659 fprintf (ira_dump_file, "\n"); 2660} 2661 2662/* Put ALLOCNO in a bucket corresponding to its number and size of its 2663 conflicting allocnos and hard registers. */ 2664static void 2665put_allocno_into_bucket (ira_allocno_t allocno) 2666{ 2667 ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true; 2668 setup_allocno_available_regs_num (allocno); 2669 if (setup_left_conflict_sizes_p (allocno)) 2670 add_allocno_to_bucket (allocno, &colorable_allocno_bucket); 2671 else 2672 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket); 2673} 2674 2675/* Map: allocno number -> allocno priority. */ 2676static int *allocno_priorities; 2677 2678/* Set up priorities for N allocnos in array 2679 CONSIDERATION_ALLOCNOS. */ 2680static void 2681setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n) 2682{ 2683 int i, length, nrefs, priority, max_priority, mult; 2684 ira_allocno_t a; 2685 2686 max_priority = 0; 2687 for (i = 0; i < n; i++) 2688 { 2689 a = consideration_allocnos[i]; 2690 nrefs = ALLOCNO_NREFS (a); 2691 ira_assert (nrefs >= 0); 2692 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1; 2693 ira_assert (mult >= 0); 2694 allocno_priorities[ALLOCNO_NUM (a)] 2695 = priority 2696 = (mult 2697 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)) 2698 * ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]); 2699 if (priority < 0) 2700 priority = -priority; 2701 if (max_priority < priority) 2702 max_priority = priority; 2703 } 2704 mult = max_priority == 0 ? 1 : INT_MAX / max_priority; 2705 for (i = 0; i < n; i++) 2706 { 2707 a = consideration_allocnos[i]; 2708 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 2709 if (ALLOCNO_NUM_OBJECTS (a) > 1) 2710 length /= ALLOCNO_NUM_OBJECTS (a); 2711 if (length <= 0) 2712 length = 1; 2713 allocno_priorities[ALLOCNO_NUM (a)] 2714 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length; 2715 } 2716} 2717 2718/* Sort allocnos according to the profit of usage of a hard register 2719 instead of memory for them. */ 2720static int 2721allocno_cost_compare_func (const void *v1p, const void *v2p) 2722{ 2723 ira_allocno_t p1 = *(const ira_allocno_t *) v1p; 2724 ira_allocno_t p2 = *(const ira_allocno_t *) v2p; 2725 int c1, c2; 2726 2727 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1); 2728 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2); 2729 if (c1 - c2) 2730 return c1 - c2; 2731 2732 /* If regs are equally good, sort by allocno numbers, so that the 2733 results of qsort leave nothing to chance. */ 2734 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2); 2735} 2736 2737/* We used Chaitin-Briggs coloring to assign as many pseudos as 2738 possible to hard registers. Let us try to improve allocation with 2739 cost point of view. This function improves the allocation by 2740 spilling some allocnos and assigning the freed hard registers to 2741 other allocnos if it decreases the overall allocation cost. */ 2742static void 2743improve_allocation (void) 2744{ 2745 unsigned int i; 2746 int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords; 2747 int check, spill_cost, min_cost, nregs, conflict_nregs, r, best; 2748 bool try_p; 2749 enum reg_class aclass; 2750 machine_mode mode; 2751 int *allocno_costs; 2752 int costs[FIRST_PSEUDO_REGISTER]; 2753 HARD_REG_SET conflicting_regs[2], profitable_hard_regs; 2754 ira_allocno_t a; 2755 bitmap_iterator bi; 2756 2757 /* Clear counts used to process conflicting allocnos only once for 2758 each allocno. */ 2759 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 2760 ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0; 2761 check = n = 0; 2762 /* Process each allocno and try to assign a hard register to it by 2763 spilling some its conflicting allocnos. */ 2764 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 2765 { 2766 a = ira_allocnos[i]; 2767 ALLOCNO_COLOR_DATA (a)->temp = 0; 2768 if (empty_profitable_hard_regs (a)) 2769 continue; 2770 check++; 2771 aclass = ALLOCNO_CLASS (a); 2772 allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a); 2773 if (allocno_costs == NULL) 2774 allocno_costs = ALLOCNO_HARD_REG_COSTS (a); 2775 if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0) 2776 base_cost = ALLOCNO_UPDATED_MEMORY_COST (a); 2777 else if (allocno_costs == NULL) 2778 /* It means that assigning a hard register is not profitable 2779 (we don't waste memory for hard register costs in this 2780 case). */ 2781 continue; 2782 else 2783 base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]]; 2784 try_p = false; 2785 get_conflict_and_start_profitable_regs (a, false, 2786 conflicting_regs, 2787 &profitable_hard_regs); 2788 class_size = ira_class_hard_regs_num[aclass]; 2789 /* Set up cost improvement for usage of each profitable hard 2790 register for allocno A. */ 2791 for (j = 0; j < class_size; j++) 2792 { 2793 hregno = ira_class_hard_regs[aclass][j]; 2794 if (! check_hard_reg_p (a, hregno, 2795 conflicting_regs, profitable_hard_regs)) 2796 continue; 2797 ira_assert (ira_class_hard_reg_index[aclass][hregno] == j); 2798 k = allocno_costs == NULL ? 0 : j; 2799 costs[hregno] = (allocno_costs == NULL 2800 ? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]); 2801 costs[hregno] -= base_cost; 2802 if (costs[hregno] < 0) 2803 try_p = true; 2804 } 2805 if (! try_p) 2806 /* There is no chance to improve the allocation cost by 2807 assigning hard register to allocno A even without spilling 2808 conflicting allocnos. */ 2809 continue; 2810 mode = ALLOCNO_MODE (a); 2811 nwords = ALLOCNO_NUM_OBJECTS (a); 2812 /* Process each allocno conflicting with A and update the cost 2813 improvement for profitable hard registers of A. To use a 2814 hard register for A we need to spill some conflicting 2815 allocnos and that creates penalty for the cost 2816 improvement. */ 2817 for (word = 0; word < nwords; word++) 2818 { 2819 ira_object_t conflict_obj; 2820 ira_object_t obj = ALLOCNO_OBJECT (a, word); 2821 ira_object_conflict_iterator oci; 2822 2823 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 2824 { 2825 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 2826 2827 if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check) 2828 /* We already processed this conflicting allocno 2829 because we processed earlier another object of the 2830 conflicting allocno. */ 2831 continue; 2832 ALLOCNO_COLOR_DATA (conflict_a)->temp = check; 2833 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0) 2834 continue; 2835 spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a); 2836 k = (ira_class_hard_reg_index 2837 [ALLOCNO_CLASS (conflict_a)][conflict_hregno]); 2838 ira_assert (k >= 0); 2839 if ((allocno_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (conflict_a)) 2840 != NULL) 2841 spill_cost -= allocno_costs[k]; 2842 else if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a)) 2843 != NULL) 2844 spill_cost -= allocno_costs[k]; 2845 else 2846 spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a); 2847 conflict_nregs 2848 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)]; 2849 for (r = conflict_hregno; 2850 r >= 0 && r + hard_regno_nregs[r][mode] > conflict_hregno; 2851 r--) 2852 if (check_hard_reg_p (a, r, 2853 conflicting_regs, profitable_hard_regs)) 2854 costs[r] += spill_cost; 2855 for (r = conflict_hregno + 1; 2856 r < conflict_hregno + conflict_nregs; 2857 r++) 2858 if (check_hard_reg_p (a, r, 2859 conflicting_regs, profitable_hard_regs)) 2860 costs[r] += spill_cost; 2861 } 2862 } 2863 min_cost = INT_MAX; 2864 best = -1; 2865 /* Now we choose hard register for A which results in highest 2866 allocation cost improvement. */ 2867 for (j = 0; j < class_size; j++) 2868 { 2869 hregno = ira_class_hard_regs[aclass][j]; 2870 if (check_hard_reg_p (a, hregno, 2871 conflicting_regs, profitable_hard_regs) 2872 && min_cost > costs[hregno]) 2873 { 2874 best = hregno; 2875 min_cost = costs[hregno]; 2876 } 2877 } 2878 if (min_cost >= 0) 2879 /* We are in a situation when assigning any hard register to A 2880 by spilling some conflicting allocnos does not improve the 2881 allocation cost. */ 2882 continue; 2883 nregs = hard_regno_nregs[best][mode]; 2884 /* Now spill conflicting allocnos which contain a hard register 2885 of A when we assign the best chosen hard register to it. */ 2886 for (word = 0; word < nwords; word++) 2887 { 2888 ira_object_t conflict_obj; 2889 ira_object_t obj = ALLOCNO_OBJECT (a, word); 2890 ira_object_conflict_iterator oci; 2891 2892 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 2893 { 2894 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 2895 2896 if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0) 2897 continue; 2898 conflict_nregs 2899 = hard_regno_nregs[conflict_hregno][ALLOCNO_MODE (conflict_a)]; 2900 if (best + nregs <= conflict_hregno 2901 || conflict_hregno + conflict_nregs <= best) 2902 /* No intersection. */ 2903 continue; 2904 ALLOCNO_HARD_REGNO (conflict_a) = -1; 2905 sorted_allocnos[n++] = conflict_a; 2906 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 2907 fprintf (ira_dump_file, "Spilling a%dr%d for a%dr%d\n", 2908 ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a), 2909 ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 2910 } 2911 } 2912 /* Assign the best chosen hard register to A. */ 2913 ALLOCNO_HARD_REGNO (a) = best; 2914 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 2915 fprintf (ira_dump_file, "Assigning %d to a%dr%d\n", 2916 best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 2917 } 2918 if (n == 0) 2919 return; 2920 /* We spilled some allocnos to assign their hard registers to other 2921 allocnos. The spilled allocnos are now in array 2922 'sorted_allocnos'. There is still a possibility that some of the 2923 spilled allocnos can get hard registers. So let us try assign 2924 them hard registers again (just a reminder -- function 2925 'assign_hard_reg' assigns hard registers only if it is possible 2926 and profitable). We process the spilled allocnos with biggest 2927 benefit to get hard register first -- see function 2928 'allocno_cost_compare_func'. */ 2929 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), 2930 allocno_cost_compare_func); 2931 for (j = 0; j < n; j++) 2932 { 2933 a = sorted_allocnos[j]; 2934 ALLOCNO_ASSIGNED_P (a) = false; 2935 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2936 { 2937 fprintf (ira_dump_file, " "); 2938 ira_print_expanded_allocno (a); 2939 fprintf (ira_dump_file, " -- "); 2940 } 2941 if (assign_hard_reg (a, false)) 2942 { 2943 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2944 fprintf (ira_dump_file, "assign hard reg %d\n", 2945 ALLOCNO_HARD_REGNO (a)); 2946 } 2947 else 2948 { 2949 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2950 fprintf (ira_dump_file, "assign memory\n"); 2951 } 2952 } 2953} 2954 2955/* Sort allocnos according to their priorities. */ 2956static int 2957allocno_priority_compare_func (const void *v1p, const void *v2p) 2958{ 2959 ira_allocno_t a1 = *(const ira_allocno_t *) v1p; 2960 ira_allocno_t a2 = *(const ira_allocno_t *) v2p; 2961 int pri1, pri2; 2962 2963 pri1 = allocno_priorities[ALLOCNO_NUM (a1)]; 2964 pri2 = allocno_priorities[ALLOCNO_NUM (a2)]; 2965 if (pri2 != pri1) 2966 return SORTGT (pri2, pri1); 2967 2968 /* If regs are equally good, sort by allocnos, so that the results of 2969 qsort leave nothing to chance. */ 2970 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); 2971} 2972 2973/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP 2974 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */ 2975static void 2976color_allocnos (void) 2977{ 2978 unsigned int i, n; 2979 bitmap_iterator bi; 2980 ira_allocno_t a; 2981 2982 setup_profitable_hard_regs (); 2983 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 2984 { 2985 int l, nr; 2986 HARD_REG_SET conflict_hard_regs; 2987 allocno_color_data_t data; 2988 ira_pref_t pref, next_pref; 2989 2990 a = ira_allocnos[i]; 2991 nr = ALLOCNO_NUM_OBJECTS (a); 2992 CLEAR_HARD_REG_SET (conflict_hard_regs); 2993 for (l = 0; l < nr; l++) 2994 { 2995 ira_object_t obj = ALLOCNO_OBJECT (a, l); 2996 IOR_HARD_REG_SET (conflict_hard_regs, 2997 OBJECT_CONFLICT_HARD_REGS (obj)); 2998 } 2999 data = ALLOCNO_COLOR_DATA (a); 3000 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref) 3001 { 3002 next_pref = pref->next_pref; 3003 if (! ira_hard_reg_in_set_p (pref->hard_regno, 3004 ALLOCNO_MODE (a), 3005 data->profitable_hard_regs)) 3006 ira_remove_pref (pref); 3007 } 3008 } 3009 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY) 3010 { 3011 n = 0; 3012 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 3013 { 3014 a = ira_allocnos[i]; 3015 if (ALLOCNO_CLASS (a) == NO_REGS) 3016 { 3017 ALLOCNO_HARD_REGNO (a) = -1; 3018 ALLOCNO_ASSIGNED_P (a) = true; 3019 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); 3020 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); 3021 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3022 { 3023 fprintf (ira_dump_file, " Spill"); 3024 ira_print_expanded_allocno (a); 3025 fprintf (ira_dump_file, "\n"); 3026 } 3027 continue; 3028 } 3029 sorted_allocnos[n++] = a; 3030 } 3031 if (n != 0) 3032 { 3033 setup_allocno_priorities (sorted_allocnos, n); 3034 qsort (sorted_allocnos, n, sizeof (ira_allocno_t), 3035 allocno_priority_compare_func); 3036 for (i = 0; i < n; i++) 3037 { 3038 a = sorted_allocnos[i]; 3039 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3040 { 3041 fprintf (ira_dump_file, " "); 3042 ira_print_expanded_allocno (a); 3043 fprintf (ira_dump_file, " -- "); 3044 } 3045 if (assign_hard_reg (a, false)) 3046 { 3047 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3048 fprintf (ira_dump_file, "assign hard reg %d\n", 3049 ALLOCNO_HARD_REGNO (a)); 3050 } 3051 else 3052 { 3053 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3054 fprintf (ira_dump_file, "assign memory\n"); 3055 } 3056 } 3057 } 3058 } 3059 else 3060 { 3061 form_allocno_hard_regs_nodes_forest (); 3062 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 3063 print_hard_regs_forest (ira_dump_file); 3064 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 3065 { 3066 a = ira_allocnos[i]; 3067 if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a)) 3068 { 3069 ALLOCNO_COLOR_DATA (a)->in_graph_p = true; 3070 update_costs_from_prefs (a); 3071 } 3072 else 3073 { 3074 ALLOCNO_HARD_REGNO (a) = -1; 3075 ALLOCNO_ASSIGNED_P (a) = true; 3076 /* We don't need updated costs anymore. */ 3077 ira_free_allocno_updated_costs (a); 3078 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3079 { 3080 fprintf (ira_dump_file, " Spill"); 3081 ira_print_expanded_allocno (a); 3082 fprintf (ira_dump_file, "\n"); 3083 } 3084 } 3085 } 3086 /* Put the allocnos into the corresponding buckets. */ 3087 colorable_allocno_bucket = NULL; 3088 uncolorable_allocno_bucket = NULL; 3089 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) 3090 { 3091 a = ira_allocnos[i]; 3092 if (ALLOCNO_COLOR_DATA (a)->in_graph_p) 3093 put_allocno_into_bucket (a); 3094 } 3095 push_allocnos_to_stack (); 3096 pop_allocnos_from_stack (); 3097 finish_allocno_hard_regs_nodes_forest (); 3098 } 3099 improve_allocation (); 3100} 3101 3102 3103 3104/* Output information about the loop given by its LOOP_TREE_NODE. */ 3105static void 3106print_loop_title (ira_loop_tree_node_t loop_tree_node) 3107{ 3108 unsigned int j; 3109 bitmap_iterator bi; 3110 ira_loop_tree_node_t subloop_node, dest_loop_node; 3111 edge e; 3112 edge_iterator ei; 3113 3114 if (loop_tree_node->parent == NULL) 3115 fprintf (ira_dump_file, 3116 "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:", 3117 NUM_FIXED_BLOCKS); 3118 else 3119 { 3120 ira_assert (current_loops != NULL && loop_tree_node->loop != NULL); 3121 fprintf (ira_dump_file, 3122 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:", 3123 loop_tree_node->loop_num, loop_tree_node->parent->loop_num, 3124 loop_tree_node->loop->header->index, 3125 loop_depth (loop_tree_node->loop)); 3126 } 3127 for (subloop_node = loop_tree_node->children; 3128 subloop_node != NULL; 3129 subloop_node = subloop_node->next) 3130 if (subloop_node->bb != NULL) 3131 { 3132 fprintf (ira_dump_file, " %d", subloop_node->bb->index); 3133 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs) 3134 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 3135 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent) 3136 != loop_tree_node)) 3137 fprintf (ira_dump_file, "(->%d:l%d)", 3138 e->dest->index, dest_loop_node->loop_num); 3139 } 3140 fprintf (ira_dump_file, "\n all:"); 3141 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) 3142 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j])); 3143 fprintf (ira_dump_file, "\n modified regnos:"); 3144 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi) 3145 fprintf (ira_dump_file, " %d", j); 3146 fprintf (ira_dump_file, "\n border:"); 3147 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi) 3148 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j])); 3149 fprintf (ira_dump_file, "\n Pressure:"); 3150 for (j = 0; (int) j < ira_pressure_classes_num; j++) 3151 { 3152 enum reg_class pclass; 3153 3154 pclass = ira_pressure_classes[j]; 3155 if (loop_tree_node->reg_pressure[pclass] == 0) 3156 continue; 3157 fprintf (ira_dump_file, " %s=%d", reg_class_names[pclass], 3158 loop_tree_node->reg_pressure[pclass]); 3159 } 3160 fprintf (ira_dump_file, "\n"); 3161} 3162 3163/* Color the allocnos inside loop (in the extreme case it can be all 3164 of the function) given the corresponding LOOP_TREE_NODE. The 3165 function is called for each loop during top-down traverse of the 3166 loop tree. */ 3167static void 3168color_pass (ira_loop_tree_node_t loop_tree_node) 3169{ 3170 int regno, hard_regno, index = -1, n; 3171 int cost, exit_freq, enter_freq; 3172 unsigned int j; 3173 bitmap_iterator bi; 3174 machine_mode mode; 3175 enum reg_class rclass, aclass, pclass; 3176 ira_allocno_t a, subloop_allocno; 3177 ira_loop_tree_node_t subloop_node; 3178 3179 ira_assert (loop_tree_node->bb == NULL); 3180 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 3181 print_loop_title (loop_tree_node); 3182 3183 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos); 3184 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap); 3185 n = 0; 3186 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) 3187 { 3188 a = ira_allocnos[j]; 3189 n++; 3190 if (! ALLOCNO_ASSIGNED_P (a)) 3191 continue; 3192 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a)); 3193 } 3194 allocno_color_data 3195 = (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data) 3196 * n); 3197 memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n); 3198 curr_allocno_process = 0; 3199 n = 0; 3200 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) 3201 { 3202 a = ira_allocnos[j]; 3203 ALLOCNO_ADD_DATA (a) = allocno_color_data + n; 3204 n++; 3205 } 3206 init_allocno_threads (); 3207 /* Color all mentioned allocnos including transparent ones. */ 3208 color_allocnos (); 3209 /* Process caps. They are processed just once. */ 3210 if (flag_ira_region == IRA_REGION_MIXED 3211 || flag_ira_region == IRA_REGION_ALL) 3212 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) 3213 { 3214 a = ira_allocnos[j]; 3215 if (ALLOCNO_CAP_MEMBER (a) == NULL) 3216 continue; 3217 /* Remove from processing in the next loop. */ 3218 bitmap_clear_bit (consideration_allocno_bitmap, j); 3219 rclass = ALLOCNO_CLASS (a); 3220 pclass = ira_pressure_class_translate[rclass]; 3221 if (flag_ira_region == IRA_REGION_MIXED 3222 && (loop_tree_node->reg_pressure[pclass] 3223 <= ira_class_hard_regs_num[pclass])) 3224 { 3225 mode = ALLOCNO_MODE (a); 3226 hard_regno = ALLOCNO_HARD_REGNO (a); 3227 if (hard_regno >= 0) 3228 { 3229 index = ira_class_hard_reg_index[rclass][hard_regno]; 3230 ira_assert (index >= 0); 3231 } 3232 regno = ALLOCNO_REGNO (a); 3233 subloop_allocno = ALLOCNO_CAP_MEMBER (a); 3234 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno); 3235 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno)); 3236 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; 3237 ALLOCNO_ASSIGNED_P (subloop_allocno) = true; 3238 if (hard_regno >= 0) 3239 update_costs_from_copies (subloop_allocno, true, true); 3240 /* We don't need updated costs anymore. */ 3241 ira_free_allocno_updated_costs (subloop_allocno); 3242 } 3243 } 3244 /* Update costs of the corresponding allocnos (not caps) in the 3245 subloops. */ 3246 for (subloop_node = loop_tree_node->subloops; 3247 subloop_node != NULL; 3248 subloop_node = subloop_node->subloop_next) 3249 { 3250 ira_assert (subloop_node->bb == NULL); 3251 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) 3252 { 3253 a = ira_allocnos[j]; 3254 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 3255 mode = ALLOCNO_MODE (a); 3256 rclass = ALLOCNO_CLASS (a); 3257 pclass = ira_pressure_class_translate[rclass]; 3258 hard_regno = ALLOCNO_HARD_REGNO (a); 3259 /* Use hard register class here. ??? */ 3260 if (hard_regno >= 0) 3261 { 3262 index = ira_class_hard_reg_index[rclass][hard_regno]; 3263 ira_assert (index >= 0); 3264 } 3265 regno = ALLOCNO_REGNO (a); 3266 /* ??? conflict costs */ 3267 subloop_allocno = subloop_node->regno_allocno_map[regno]; 3268 if (subloop_allocno == NULL 3269 || ALLOCNO_CAP (subloop_allocno) != NULL) 3270 continue; 3271 ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass); 3272 ira_assert (bitmap_bit_p (subloop_node->all_allocnos, 3273 ALLOCNO_NUM (subloop_allocno))); 3274 if ((flag_ira_region == IRA_REGION_MIXED 3275 && (loop_tree_node->reg_pressure[pclass] 3276 <= ira_class_hard_regs_num[pclass])) 3277 || (pic_offset_table_rtx != NULL 3278 && regno == (int) REGNO (pic_offset_table_rtx)) 3279 /* Avoid overlapped multi-registers. Moves between them 3280 might result in wrong code generation. */ 3281 || (hard_regno >= 0 3282 && ira_reg_class_max_nregs[pclass][mode] > 1)) 3283 { 3284 if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) 3285 { 3286 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; 3287 ALLOCNO_ASSIGNED_P (subloop_allocno) = true; 3288 if (hard_regno >= 0) 3289 update_costs_from_copies (subloop_allocno, true, true); 3290 /* We don't need updated costs anymore. */ 3291 ira_free_allocno_updated_costs (subloop_allocno); 3292 } 3293 continue; 3294 } 3295 exit_freq = ira_loop_edge_freq (subloop_node, regno, true); 3296 enter_freq = ira_loop_edge_freq (subloop_node, regno, false); 3297 ira_assert (regno < ira_reg_equiv_len); 3298 if (ira_equiv_no_lvalue_p (regno)) 3299 { 3300 if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) 3301 { 3302 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; 3303 ALLOCNO_ASSIGNED_P (subloop_allocno) = true; 3304 if (hard_regno >= 0) 3305 update_costs_from_copies (subloop_allocno, true, true); 3306 /* We don't need updated costs anymore. */ 3307 ira_free_allocno_updated_costs (subloop_allocno); 3308 } 3309 } 3310 else if (hard_regno < 0) 3311 { 3312 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) 3313 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq) 3314 + (ira_memory_move_cost[mode][rclass][0] * exit_freq)); 3315 } 3316 else 3317 { 3318 aclass = ALLOCNO_CLASS (subloop_allocno); 3319 ira_init_register_move_cost_if_necessary (mode); 3320 cost = (ira_register_move_cost[mode][rclass][rclass] 3321 * (exit_freq + enter_freq)); 3322 ira_allocate_and_set_or_copy_costs 3323 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass, 3324 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno), 3325 ALLOCNO_HARD_REG_COSTS (subloop_allocno)); 3326 ira_allocate_and_set_or_copy_costs 3327 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno), 3328 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)); 3329 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost; 3330 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index] 3331 -= cost; 3332 if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno) 3333 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index]) 3334 ALLOCNO_UPDATED_CLASS_COST (subloop_allocno) 3335 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index]; 3336 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) 3337 += (ira_memory_move_cost[mode][rclass][0] * enter_freq 3338 + ira_memory_move_cost[mode][rclass][1] * exit_freq); 3339 } 3340 } 3341 } 3342 ira_free (allocno_color_data); 3343 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) 3344 { 3345 a = ira_allocnos[j]; 3346 ALLOCNO_ADD_DATA (a) = NULL; 3347 } 3348} 3349 3350/* Initialize the common data for coloring and calls functions to do 3351 Chaitin-Briggs and regional coloring. */ 3352static void 3353do_coloring (void) 3354{ 3355 coloring_allocno_bitmap = ira_allocate_bitmap (); 3356 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 3357 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n"); 3358 3359 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL); 3360 3361 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 3362 ira_print_disposition (ira_dump_file); 3363 3364 ira_free_bitmap (coloring_allocno_bitmap); 3365} 3366 3367 3368 3369/* Move spill/restore code, which are to be generated in ira-emit.c, 3370 to less frequent points (if it is profitable) by reassigning some 3371 allocnos (in loop with subloops containing in another loop) to 3372 memory which results in longer live-range where the corresponding 3373 pseudo-registers will be in memory. */ 3374static void 3375move_spill_restore (void) 3376{ 3377 int cost, regno, hard_regno, hard_regno2, index; 3378 bool changed_p; 3379 int enter_freq, exit_freq; 3380 machine_mode mode; 3381 enum reg_class rclass; 3382 ira_allocno_t a, parent_allocno, subloop_allocno; 3383 ira_loop_tree_node_t parent, loop_node, subloop_node; 3384 ira_allocno_iterator ai; 3385 3386 for (;;) 3387 { 3388 changed_p = false; 3389 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 3390 fprintf (ira_dump_file, "New iteration of spill/restore move\n"); 3391 FOR_EACH_ALLOCNO (a, ai) 3392 { 3393 regno = ALLOCNO_REGNO (a); 3394 loop_node = ALLOCNO_LOOP_TREE_NODE (a); 3395 if (ALLOCNO_CAP_MEMBER (a) != NULL 3396 || ALLOCNO_CAP (a) != NULL 3397 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0 3398 || loop_node->children == NULL 3399 /* don't do the optimization because it can create 3400 copies and the reload pass can spill the allocno set 3401 by copy although the allocno will not get memory 3402 slot. */ 3403 || ira_equiv_no_lvalue_p (regno) 3404 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))) 3405 continue; 3406 mode = ALLOCNO_MODE (a); 3407 rclass = ALLOCNO_CLASS (a); 3408 index = ira_class_hard_reg_index[rclass][hard_regno]; 3409 ira_assert (index >= 0); 3410 cost = (ALLOCNO_MEMORY_COST (a) 3411 - (ALLOCNO_HARD_REG_COSTS (a) == NULL 3412 ? ALLOCNO_CLASS_COST (a) 3413 : ALLOCNO_HARD_REG_COSTS (a)[index])); 3414 ira_init_register_move_cost_if_necessary (mode); 3415 for (subloop_node = loop_node->subloops; 3416 subloop_node != NULL; 3417 subloop_node = subloop_node->subloop_next) 3418 { 3419 ira_assert (subloop_node->bb == NULL); 3420 subloop_allocno = subloop_node->regno_allocno_map[regno]; 3421 if (subloop_allocno == NULL) 3422 continue; 3423 ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno)); 3424 /* We have accumulated cost. To get the real cost of 3425 allocno usage in the loop we should subtract costs of 3426 the subloop allocnos. */ 3427 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno) 3428 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL 3429 ? ALLOCNO_CLASS_COST (subloop_allocno) 3430 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])); 3431 exit_freq = ira_loop_edge_freq (subloop_node, regno, true); 3432 enter_freq = ira_loop_edge_freq (subloop_node, regno, false); 3433 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0) 3434 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq 3435 + ira_memory_move_cost[mode][rclass][1] * enter_freq); 3436 else 3437 { 3438 cost 3439 += (ira_memory_move_cost[mode][rclass][0] * exit_freq 3440 + ira_memory_move_cost[mode][rclass][1] * enter_freq); 3441 if (hard_regno2 != hard_regno) 3442 cost -= (ira_register_move_cost[mode][rclass][rclass] 3443 * (exit_freq + enter_freq)); 3444 } 3445 } 3446 if ((parent = loop_node->parent) != NULL 3447 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL) 3448 { 3449 ira_assert (rclass == ALLOCNO_CLASS (parent_allocno)); 3450 exit_freq = ira_loop_edge_freq (loop_node, regno, true); 3451 enter_freq = ira_loop_edge_freq (loop_node, regno, false); 3452 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0) 3453 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq 3454 + ira_memory_move_cost[mode][rclass][1] * enter_freq); 3455 else 3456 { 3457 cost 3458 += (ira_memory_move_cost[mode][rclass][1] * exit_freq 3459 + ira_memory_move_cost[mode][rclass][0] * enter_freq); 3460 if (hard_regno2 != hard_regno) 3461 cost -= (ira_register_move_cost[mode][rclass][rclass] 3462 * (exit_freq + enter_freq)); 3463 } 3464 } 3465 if (cost < 0) 3466 { 3467 ALLOCNO_HARD_REGNO (a) = -1; 3468 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3469 { 3470 fprintf 3471 (ira_dump_file, 3472 " Moving spill/restore for a%dr%d up from loop %d", 3473 ALLOCNO_NUM (a), regno, loop_node->loop_num); 3474 fprintf (ira_dump_file, " - profit %d\n", -cost); 3475 } 3476 changed_p = true; 3477 } 3478 } 3479 if (! changed_p) 3480 break; 3481 } 3482} 3483 3484 3485 3486/* Update current hard reg costs and current conflict hard reg costs 3487 for allocno A. It is done by processing its copies containing 3488 other allocnos already assigned. */ 3489static void 3490update_curr_costs (ira_allocno_t a) 3491{ 3492 int i, hard_regno, cost; 3493 machine_mode mode; 3494 enum reg_class aclass, rclass; 3495 ira_allocno_t another_a; 3496 ira_copy_t cp, next_cp; 3497 3498 ira_free_allocno_updated_costs (a); 3499 ira_assert (! ALLOCNO_ASSIGNED_P (a)); 3500 aclass = ALLOCNO_CLASS (a); 3501 if (aclass == NO_REGS) 3502 return; 3503 mode = ALLOCNO_MODE (a); 3504 ira_init_register_move_cost_if_necessary (mode); 3505 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 3506 { 3507 if (cp->first == a) 3508 { 3509 next_cp = cp->next_first_allocno_copy; 3510 another_a = cp->second; 3511 } 3512 else if (cp->second == a) 3513 { 3514 next_cp = cp->next_second_allocno_copy; 3515 another_a = cp->first; 3516 } 3517 else 3518 gcc_unreachable (); 3519 if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)] 3520 || ! ALLOCNO_ASSIGNED_P (another_a) 3521 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0) 3522 continue; 3523 rclass = REGNO_REG_CLASS (hard_regno); 3524 i = ira_class_hard_reg_index[aclass][hard_regno]; 3525 if (i < 0) 3526 continue; 3527 cost = (cp->first == a 3528 ? ira_register_move_cost[mode][rclass][aclass] 3529 : ira_register_move_cost[mode][aclass][rclass]); 3530 ira_allocate_and_set_or_copy_costs 3531 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a), 3532 ALLOCNO_HARD_REG_COSTS (a)); 3533 ira_allocate_and_set_or_copy_costs 3534 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), 3535 aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); 3536 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost; 3537 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost; 3538 } 3539} 3540 3541/* Try to assign hard registers to the unassigned allocnos and 3542 allocnos conflicting with them or conflicting with allocnos whose 3543 regno >= START_REGNO. The function is called after ira_flattening, 3544 so more allocnos (including ones created in ira-emit.c) will have a 3545 chance to get a hard register. We use simple assignment algorithm 3546 based on priorities. */ 3547void 3548ira_reassign_conflict_allocnos (int start_regno) 3549{ 3550 int i, allocnos_to_color_num; 3551 ira_allocno_t a; 3552 enum reg_class aclass; 3553 bitmap allocnos_to_color; 3554 ira_allocno_iterator ai; 3555 3556 allocnos_to_color = ira_allocate_bitmap (); 3557 allocnos_to_color_num = 0; 3558 FOR_EACH_ALLOCNO (a, ai) 3559 { 3560 int n = ALLOCNO_NUM_OBJECTS (a); 3561 3562 if (! ALLOCNO_ASSIGNED_P (a) 3563 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a))) 3564 { 3565 if (ALLOCNO_CLASS (a) != NO_REGS) 3566 sorted_allocnos[allocnos_to_color_num++] = a; 3567 else 3568 { 3569 ALLOCNO_ASSIGNED_P (a) = true; 3570 ALLOCNO_HARD_REGNO (a) = -1; 3571 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); 3572 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); 3573 } 3574 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a)); 3575 } 3576 if (ALLOCNO_REGNO (a) < start_regno 3577 || (aclass = ALLOCNO_CLASS (a)) == NO_REGS) 3578 continue; 3579 for (i = 0; i < n; i++) 3580 { 3581 ira_object_t obj = ALLOCNO_OBJECT (a, i); 3582 ira_object_t conflict_obj; 3583 ira_object_conflict_iterator oci; 3584 3585 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 3586 { 3587 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 3588 3589 ira_assert (ira_reg_classes_intersect_p 3590 [aclass][ALLOCNO_CLASS (conflict_a)]); 3591 if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a))) 3592 continue; 3593 sorted_allocnos[allocnos_to_color_num++] = conflict_a; 3594 } 3595 } 3596 } 3597 ira_free_bitmap (allocnos_to_color); 3598 if (allocnos_to_color_num > 1) 3599 { 3600 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num); 3601 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t), 3602 allocno_priority_compare_func); 3603 } 3604 for (i = 0; i < allocnos_to_color_num; i++) 3605 { 3606 a = sorted_allocnos[i]; 3607 ALLOCNO_ASSIGNED_P (a) = false; 3608 update_curr_costs (a); 3609 } 3610 for (i = 0; i < allocnos_to_color_num; i++) 3611 { 3612 a = sorted_allocnos[i]; 3613 if (assign_hard_reg (a, true)) 3614 { 3615 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3616 fprintf 3617 (ira_dump_file, 3618 " Secondary allocation: assign hard reg %d to reg %d\n", 3619 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a)); 3620 } 3621 } 3622} 3623 3624 3625 3626/* This page contains functions used to find conflicts using allocno 3627 live ranges. */ 3628 3629#ifdef ENABLE_IRA_CHECKING 3630 3631/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2 3632 intersect. This should be used when there is only one region. 3633 Currently this is used during reload. */ 3634static bool 3635conflict_by_live_ranges_p (int regno1, int regno2) 3636{ 3637 ira_allocno_t a1, a2; 3638 3639 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER 3640 && regno2 >= FIRST_PSEUDO_REGISTER); 3641 /* Reg info calculated by dataflow infrastructure can be different 3642 from one calculated by regclass. */ 3643 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL 3644 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL) 3645 return false; 3646 return allocnos_conflict_by_live_ranges_p (a1, a2); 3647} 3648 3649#endif 3650 3651 3652 3653/* This page contains code to coalesce memory stack slots used by 3654 spilled allocnos. This results in smaller stack frame, better data 3655 locality, and in smaller code for some architectures like 3656 x86/x86_64 where insn size depends on address displacement value. 3657 On the other hand, it can worsen insn scheduling after the RA but 3658 in practice it is less important than smaller stack frames. */ 3659 3660/* TRUE if we coalesced some allocnos. In other words, if we got 3661 loops formed by members first_coalesced_allocno and 3662 next_coalesced_allocno containing more one allocno. */ 3663static bool allocno_coalesced_p; 3664 3665/* Bitmap used to prevent a repeated allocno processing because of 3666 coalescing. */ 3667static bitmap processed_coalesced_allocno_bitmap; 3668 3669/* See below. */ 3670typedef struct coalesce_data *coalesce_data_t; 3671 3672/* To decrease footprint of ira_allocno structure we store all data 3673 needed only for coalescing in the following structure. */ 3674struct coalesce_data 3675{ 3676 /* Coalesced allocnos form a cyclic list. One allocno given by 3677 FIRST represents all coalesced allocnos. The 3678 list is chained by NEXT. */ 3679 ira_allocno_t first; 3680 ira_allocno_t next; 3681 int temp; 3682}; 3683 3684/* Container for storing allocno data concerning coalescing. */ 3685static coalesce_data_t allocno_coalesce_data; 3686 3687/* Macro to access the data concerning coalescing. */ 3688#define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a)) 3689 3690/* Merge two sets of coalesced allocnos given correspondingly by 3691 allocnos A1 and A2 (more accurately merging A2 set into A1 3692 set). */ 3693static void 3694merge_allocnos (ira_allocno_t a1, ira_allocno_t a2) 3695{ 3696 ira_allocno_t a, first, last, next; 3697 3698 first = ALLOCNO_COALESCE_DATA (a1)->first; 3699 a = ALLOCNO_COALESCE_DATA (a2)->first; 3700 if (first == a) 3701 return; 3702 for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;; 3703 a = ALLOCNO_COALESCE_DATA (a)->next) 3704 { 3705 ALLOCNO_COALESCE_DATA (a)->first = first; 3706 if (a == a2) 3707 break; 3708 last = a; 3709 } 3710 next = allocno_coalesce_data[ALLOCNO_NUM (first)].next; 3711 allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2; 3712 allocno_coalesce_data[ALLOCNO_NUM (last)].next = next; 3713} 3714 3715/* Return TRUE if there are conflicting allocnos from two sets of 3716 coalesced allocnos given correspondingly by allocnos A1 and A2. We 3717 use live ranges to find conflicts because conflicts are represented 3718 only for allocnos of the same allocno class and during the reload 3719 pass we coalesce allocnos for sharing stack memory slots. */ 3720static bool 3721coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2) 3722{ 3723 ira_allocno_t a, conflict_a; 3724 3725 if (allocno_coalesced_p) 3726 { 3727 bitmap_clear (processed_coalesced_allocno_bitmap); 3728 for (a = ALLOCNO_COALESCE_DATA (a1)->next;; 3729 a = ALLOCNO_COALESCE_DATA (a)->next) 3730 { 3731 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a)); 3732 if (a == a1) 3733 break; 3734 } 3735 } 3736 for (a = ALLOCNO_COALESCE_DATA (a2)->next;; 3737 a = ALLOCNO_COALESCE_DATA (a)->next) 3738 { 3739 for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;; 3740 conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next) 3741 { 3742 if (allocnos_conflict_by_live_ranges_p (a, conflict_a)) 3743 return true; 3744 if (conflict_a == a1) 3745 break; 3746 } 3747 if (a == a2) 3748 break; 3749 } 3750 return false; 3751} 3752 3753/* The major function for aggressive allocno coalescing. We coalesce 3754 only spilled allocnos. If some allocnos have been coalesced, we 3755 set up flag allocno_coalesced_p. */ 3756static void 3757coalesce_allocnos (void) 3758{ 3759 ira_allocno_t a; 3760 ira_copy_t cp, next_cp; 3761 unsigned int j; 3762 int i, n, cp_num, regno; 3763 bitmap_iterator bi; 3764 3765 cp_num = 0; 3766 /* Collect copies. */ 3767 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi) 3768 { 3769 a = ira_allocnos[j]; 3770 regno = ALLOCNO_REGNO (a); 3771 if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0 3772 || ira_equiv_no_lvalue_p (regno)) 3773 continue; 3774 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 3775 { 3776 if (cp->first == a) 3777 { 3778 next_cp = cp->next_first_allocno_copy; 3779 regno = ALLOCNO_REGNO (cp->second); 3780 /* For priority coloring we coalesce allocnos only with 3781 the same allocno class not with intersected allocno 3782 classes as it were possible. It is done for 3783 simplicity. */ 3784 if ((cp->insn != NULL || cp->constraint_p) 3785 && ALLOCNO_ASSIGNED_P (cp->second) 3786 && ALLOCNO_HARD_REGNO (cp->second) < 0 3787 && ! ira_equiv_no_lvalue_p (regno)) 3788 sorted_copies[cp_num++] = cp; 3789 } 3790 else if (cp->second == a) 3791 next_cp = cp->next_second_allocno_copy; 3792 else 3793 gcc_unreachable (); 3794 } 3795 } 3796 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); 3797 /* Coalesced copies, most frequently executed first. */ 3798 for (; cp_num != 0;) 3799 { 3800 for (i = 0; i < cp_num; i++) 3801 { 3802 cp = sorted_copies[i]; 3803 if (! coalesced_allocno_conflict_p (cp->first, cp->second)) 3804 { 3805 allocno_coalesced_p = true; 3806 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 3807 fprintf 3808 (ira_dump_file, 3809 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n", 3810 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), 3811 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), 3812 cp->freq); 3813 merge_allocnos (cp->first, cp->second); 3814 i++; 3815 break; 3816 } 3817 } 3818 /* Collect the rest of copies. */ 3819 for (n = 0; i < cp_num; i++) 3820 { 3821 cp = sorted_copies[i]; 3822 if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first 3823 != allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first) 3824 sorted_copies[n++] = cp; 3825 } 3826 cp_num = n; 3827 } 3828} 3829 3830/* Usage cost and order number of coalesced allocno set to which 3831 given pseudo register belongs to. */ 3832static int *regno_coalesced_allocno_cost; 3833static int *regno_coalesced_allocno_num; 3834 3835/* Sort pseudos according frequencies of coalesced allocno sets they 3836 belong to (putting most frequently ones first), and according to 3837 coalesced allocno set order numbers. */ 3838static int 3839coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p) 3840{ 3841 const int regno1 = *(const int *) v1p; 3842 const int regno2 = *(const int *) v2p; 3843 int diff; 3844 3845 if ((diff = (regno_coalesced_allocno_cost[regno2] 3846 - regno_coalesced_allocno_cost[regno1])) != 0) 3847 return diff; 3848 if ((diff = (regno_coalesced_allocno_num[regno1] 3849 - regno_coalesced_allocno_num[regno2])) != 0) 3850 return diff; 3851 return regno1 - regno2; 3852} 3853 3854/* Widest width in which each pseudo reg is referred to (via subreg). 3855 It is used for sorting pseudo registers. */ 3856static unsigned int *regno_max_ref_width; 3857 3858/* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */ 3859#ifdef STACK_GROWS_DOWNWARD 3860# undef STACK_GROWS_DOWNWARD 3861# define STACK_GROWS_DOWNWARD 1 3862#else 3863# define STACK_GROWS_DOWNWARD 0 3864#endif 3865 3866/* Sort pseudos according their slot numbers (putting ones with 3867 smaller numbers first, or last when the frame pointer is not 3868 needed). */ 3869static int 3870coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p) 3871{ 3872 const int regno1 = *(const int *) v1p; 3873 const int regno2 = *(const int *) v2p; 3874 ira_allocno_t a1 = ira_regno_allocno_map[regno1]; 3875 ira_allocno_t a2 = ira_regno_allocno_map[regno2]; 3876 int diff, slot_num1, slot_num2; 3877 int total_size1, total_size2; 3878 3879 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0) 3880 { 3881 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0) 3882 return regno1 - regno2; 3883 return 1; 3884 } 3885 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0) 3886 return -1; 3887 slot_num1 = -ALLOCNO_HARD_REGNO (a1); 3888 slot_num2 = -ALLOCNO_HARD_REGNO (a2); 3889 if ((diff = slot_num1 - slot_num2) != 0) 3890 return (frame_pointer_needed 3891 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff); 3892 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), 3893 regno_max_ref_width[regno1]); 3894 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), 3895 regno_max_ref_width[regno2]); 3896 if ((diff = total_size2 - total_size1) != 0) 3897 return diff; 3898 return regno1 - regno2; 3899} 3900 3901/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM 3902 for coalesced allocno sets containing allocnos with their regnos 3903 given in array PSEUDO_REGNOS of length N. */ 3904static void 3905setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n) 3906{ 3907 int i, num, regno, cost; 3908 ira_allocno_t allocno, a; 3909 3910 for (num = i = 0; i < n; i++) 3911 { 3912 regno = pseudo_regnos[i]; 3913 allocno = ira_regno_allocno_map[regno]; 3914 if (allocno == NULL) 3915 { 3916 regno_coalesced_allocno_cost[regno] = 0; 3917 regno_coalesced_allocno_num[regno] = ++num; 3918 continue; 3919 } 3920 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno) 3921 continue; 3922 num++; 3923 for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;; 3924 a = ALLOCNO_COALESCE_DATA (a)->next) 3925 { 3926 cost += ALLOCNO_FREQ (a); 3927 if (a == allocno) 3928 break; 3929 } 3930 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;; 3931 a = ALLOCNO_COALESCE_DATA (a)->next) 3932 { 3933 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num; 3934 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost; 3935 if (a == allocno) 3936 break; 3937 } 3938 } 3939} 3940 3941/* Collect spilled allocnos representing coalesced allocno sets (the 3942 first coalesced allocno). The collected allocnos are returned 3943 through array SPILLED_COALESCED_ALLOCNOS. The function returns the 3944 number of the collected allocnos. The allocnos are given by their 3945 regnos in array PSEUDO_REGNOS of length N. */ 3946static int 3947collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n, 3948 ira_allocno_t *spilled_coalesced_allocnos) 3949{ 3950 int i, num, regno; 3951 ira_allocno_t allocno; 3952 3953 for (num = i = 0; i < n; i++) 3954 { 3955 regno = pseudo_regnos[i]; 3956 allocno = ira_regno_allocno_map[regno]; 3957 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0 3958 || ALLOCNO_COALESCE_DATA (allocno)->first != allocno) 3959 continue; 3960 spilled_coalesced_allocnos[num++] = allocno; 3961 } 3962 return num; 3963} 3964 3965/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for 3966 given slot contains live ranges of coalesced allocnos assigned to 3967 given slot. */ 3968static live_range_t *slot_coalesced_allocnos_live_ranges; 3969 3970/* Return TRUE if coalesced allocnos represented by ALLOCNO has live 3971 ranges intersected with live ranges of coalesced allocnos assigned 3972 to slot with number N. */ 3973static bool 3974slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n) 3975{ 3976 ira_allocno_t a; 3977 3978 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;; 3979 a = ALLOCNO_COALESCE_DATA (a)->next) 3980 { 3981 int i; 3982 int nr = ALLOCNO_NUM_OBJECTS (a); 3983 3984 for (i = 0; i < nr; i++) 3985 { 3986 ira_object_t obj = ALLOCNO_OBJECT (a, i); 3987 3988 if (ira_live_ranges_intersect_p 3989 (slot_coalesced_allocnos_live_ranges[n], 3990 OBJECT_LIVE_RANGES (obj))) 3991 return true; 3992 } 3993 if (a == allocno) 3994 break; 3995 } 3996 return false; 3997} 3998 3999/* Update live ranges of slot to which coalesced allocnos represented 4000 by ALLOCNO were assigned. */ 4001static void 4002setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno) 4003{ 4004 int i, n; 4005 ira_allocno_t a; 4006 live_range_t r; 4007 4008 n = ALLOCNO_COALESCE_DATA (allocno)->temp; 4009 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;; 4010 a = ALLOCNO_COALESCE_DATA (a)->next) 4011 { 4012 int nr = ALLOCNO_NUM_OBJECTS (a); 4013 for (i = 0; i < nr; i++) 4014 { 4015 ira_object_t obj = ALLOCNO_OBJECT (a, i); 4016 4017 r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj)); 4018 slot_coalesced_allocnos_live_ranges[n] 4019 = ira_merge_live_ranges 4020 (slot_coalesced_allocnos_live_ranges[n], r); 4021 } 4022 if (a == allocno) 4023 break; 4024 } 4025} 4026 4027/* We have coalesced allocnos involving in copies. Coalesce allocnos 4028 further in order to share the same memory stack slot. Allocnos 4029 representing sets of allocnos coalesced before the call are given 4030 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if 4031 some allocnos were coalesced in the function. */ 4032static bool 4033coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num) 4034{ 4035 int i, j, n, last_coalesced_allocno_num; 4036 ira_allocno_t allocno, a; 4037 bool merged_p = false; 4038 bitmap set_jump_crosses = regstat_get_setjmp_crosses (); 4039 4040 slot_coalesced_allocnos_live_ranges 4041 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num); 4042 memset (slot_coalesced_allocnos_live_ranges, 0, 4043 sizeof (live_range_t) * ira_allocnos_num); 4044 last_coalesced_allocno_num = 0; 4045 /* Coalesce non-conflicting spilled allocnos preferring most 4046 frequently used. */ 4047 for (i = 0; i < num; i++) 4048 { 4049 allocno = spilled_coalesced_allocnos[i]; 4050 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno 4051 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno)) 4052 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno))) 4053 continue; 4054 for (j = 0; j < i; j++) 4055 { 4056 a = spilled_coalesced_allocnos[j]; 4057 n = ALLOCNO_COALESCE_DATA (a)->temp; 4058 if (ALLOCNO_COALESCE_DATA (a)->first == a 4059 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a)) 4060 && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a)) 4061 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n)) 4062 break; 4063 } 4064 if (j >= i) 4065 { 4066 /* No coalescing: set up number for coalesced allocnos 4067 represented by ALLOCNO. */ 4068 ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++; 4069 setup_slot_coalesced_allocno_live_ranges (allocno); 4070 } 4071 else 4072 { 4073 allocno_coalesced_p = true; 4074 merged_p = true; 4075 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4076 fprintf (ira_dump_file, 4077 " Coalescing spilled allocnos a%dr%d->a%dr%d\n", 4078 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno), 4079 ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 4080 ALLOCNO_COALESCE_DATA (allocno)->temp 4081 = ALLOCNO_COALESCE_DATA (a)->temp; 4082 setup_slot_coalesced_allocno_live_ranges (allocno); 4083 merge_allocnos (a, allocno); 4084 ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a); 4085 } 4086 } 4087 for (i = 0; i < ira_allocnos_num; i++) 4088 ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]); 4089 ira_free (slot_coalesced_allocnos_live_ranges); 4090 return merged_p; 4091} 4092 4093/* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for 4094 subsequent assigning stack slots to them in the reload pass. To do 4095 this we coalesce spilled allocnos first to decrease the number of 4096 memory-memory move insns. This function is called by the 4097 reload. */ 4098void 4099ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, 4100 unsigned int *reg_max_ref_width) 4101{ 4102 int max_regno = max_reg_num (); 4103 int i, regno, num, slot_num; 4104 ira_allocno_t allocno, a; 4105 ira_allocno_iterator ai; 4106 ira_allocno_t *spilled_coalesced_allocnos; 4107 4108 ira_assert (! ira_use_lra_p); 4109 4110 /* Set up allocnos can be coalesced. */ 4111 coloring_allocno_bitmap = ira_allocate_bitmap (); 4112 for (i = 0; i < n; i++) 4113 { 4114 regno = pseudo_regnos[i]; 4115 allocno = ira_regno_allocno_map[regno]; 4116 if (allocno != NULL) 4117 bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno)); 4118 } 4119 allocno_coalesced_p = false; 4120 processed_coalesced_allocno_bitmap = ira_allocate_bitmap (); 4121 allocno_coalesce_data 4122 = (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data) 4123 * ira_allocnos_num); 4124 /* Initialize coalesce data for allocnos. */ 4125 FOR_EACH_ALLOCNO (a, ai) 4126 { 4127 ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a); 4128 ALLOCNO_COALESCE_DATA (a)->first = a; 4129 ALLOCNO_COALESCE_DATA (a)->next = a; 4130 } 4131 coalesce_allocnos (); 4132 ira_free_bitmap (coloring_allocno_bitmap); 4133 regno_coalesced_allocno_cost 4134 = (int *) ira_allocate (max_regno * sizeof (int)); 4135 regno_coalesced_allocno_num 4136 = (int *) ira_allocate (max_regno * sizeof (int)); 4137 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int)); 4138 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n); 4139 /* Sort regnos according frequencies of the corresponding coalesced 4140 allocno sets. */ 4141 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare); 4142 spilled_coalesced_allocnos 4143 = (ira_allocno_t *) ira_allocate (ira_allocnos_num 4144 * sizeof (ira_allocno_t)); 4145 /* Collect allocnos representing the spilled coalesced allocno 4146 sets. */ 4147 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n, 4148 spilled_coalesced_allocnos); 4149 if (flag_ira_share_spill_slots 4150 && coalesce_spill_slots (spilled_coalesced_allocnos, num)) 4151 { 4152 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n); 4153 qsort (pseudo_regnos, n, sizeof (int), 4154 coalesced_pseudo_reg_freq_compare); 4155 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n, 4156 spilled_coalesced_allocnos); 4157 } 4158 ira_free_bitmap (processed_coalesced_allocno_bitmap); 4159 allocno_coalesced_p = false; 4160 /* Assign stack slot numbers to spilled allocno sets, use smaller 4161 numbers for most frequently used coalesced allocnos. -1 is 4162 reserved for dynamic search of stack slots for pseudos spilled by 4163 the reload. */ 4164 slot_num = 1; 4165 for (i = 0; i < num; i++) 4166 { 4167 allocno = spilled_coalesced_allocnos[i]; 4168 if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno 4169 || ALLOCNO_HARD_REGNO (allocno) >= 0 4170 || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno))) 4171 continue; 4172 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4173 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num); 4174 slot_num++; 4175 for (a = ALLOCNO_COALESCE_DATA (allocno)->next;; 4176 a = ALLOCNO_COALESCE_DATA (a)->next) 4177 { 4178 ira_assert (ALLOCNO_HARD_REGNO (a) < 0); 4179 ALLOCNO_HARD_REGNO (a) = -slot_num; 4180 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4181 fprintf (ira_dump_file, " a%dr%d(%d,%d)", 4182 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a), 4183 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)), 4184 reg_max_ref_width[ALLOCNO_REGNO (a)])); 4185 4186 if (a == allocno) 4187 break; 4188 } 4189 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4190 fprintf (ira_dump_file, "\n"); 4191 } 4192 ira_spilled_reg_stack_slots_num = slot_num - 1; 4193 ira_free (spilled_coalesced_allocnos); 4194 /* Sort regnos according the slot numbers. */ 4195 regno_max_ref_width = reg_max_ref_width; 4196 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare); 4197 FOR_EACH_ALLOCNO (a, ai) 4198 ALLOCNO_ADD_DATA (a) = NULL; 4199 ira_free (allocno_coalesce_data); 4200 ira_free (regno_coalesced_allocno_num); 4201 ira_free (regno_coalesced_allocno_cost); 4202} 4203 4204 4205 4206/* This page contains code used by the reload pass to improve the 4207 final code. */ 4208 4209/* The function is called from reload to mark changes in the 4210 allocation of REGNO made by the reload. Remember that reg_renumber 4211 reflects the change result. */ 4212void 4213ira_mark_allocation_change (int regno) 4214{ 4215 ira_allocno_t a = ira_regno_allocno_map[regno]; 4216 int old_hard_regno, hard_regno, cost; 4217 enum reg_class aclass = ALLOCNO_CLASS (a); 4218 4219 ira_assert (a != NULL); 4220 hard_regno = reg_renumber[regno]; 4221 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno) 4222 return; 4223 if (old_hard_regno < 0) 4224 cost = -ALLOCNO_MEMORY_COST (a); 4225 else 4226 { 4227 ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0); 4228 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL 4229 ? ALLOCNO_CLASS_COST (a) 4230 : ALLOCNO_HARD_REG_COSTS (a) 4231 [ira_class_hard_reg_index[aclass][old_hard_regno]]); 4232 update_costs_from_copies (a, false, false); 4233 } 4234 ira_overall_cost -= cost; 4235 ALLOCNO_HARD_REGNO (a) = hard_regno; 4236 if (hard_regno < 0) 4237 { 4238 ALLOCNO_HARD_REGNO (a) = -1; 4239 cost += ALLOCNO_MEMORY_COST (a); 4240 } 4241 else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0) 4242 { 4243 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL 4244 ? ALLOCNO_CLASS_COST (a) 4245 : ALLOCNO_HARD_REG_COSTS (a) 4246 [ira_class_hard_reg_index[aclass][hard_regno]]); 4247 update_costs_from_copies (a, true, false); 4248 } 4249 else 4250 /* Reload changed class of the allocno. */ 4251 cost = 0; 4252 ira_overall_cost += cost; 4253} 4254 4255/* This function is called when reload deletes memory-memory move. In 4256 this case we marks that the allocation of the corresponding 4257 allocnos should be not changed in future. Otherwise we risk to get 4258 a wrong code. */ 4259void 4260ira_mark_memory_move_deletion (int dst_regno, int src_regno) 4261{ 4262 ira_allocno_t dst = ira_regno_allocno_map[dst_regno]; 4263 ira_allocno_t src = ira_regno_allocno_map[src_regno]; 4264 4265 ira_assert (dst != NULL && src != NULL 4266 && ALLOCNO_HARD_REGNO (dst) < 0 4267 && ALLOCNO_HARD_REGNO (src) < 0); 4268 ALLOCNO_DONT_REASSIGN_P (dst) = true; 4269 ALLOCNO_DONT_REASSIGN_P (src) = true; 4270} 4271 4272/* Try to assign a hard register (except for FORBIDDEN_REGS) to 4273 allocno A and return TRUE in the case of success. */ 4274static bool 4275allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs) 4276{ 4277 int hard_regno; 4278 enum reg_class aclass; 4279 int regno = ALLOCNO_REGNO (a); 4280 HARD_REG_SET saved[2]; 4281 int i, n; 4282 4283 n = ALLOCNO_NUM_OBJECTS (a); 4284 for (i = 0; i < n; i++) 4285 { 4286 ira_object_t obj = ALLOCNO_OBJECT (a, i); 4287 COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 4288 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs); 4289 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 4290 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 4291 call_used_reg_set); 4292 } 4293 ALLOCNO_ASSIGNED_P (a) = false; 4294 aclass = ALLOCNO_CLASS (a); 4295 update_curr_costs (a); 4296 assign_hard_reg (a, true); 4297 hard_regno = ALLOCNO_HARD_REGNO (a); 4298 reg_renumber[regno] = hard_regno; 4299 if (hard_regno < 0) 4300 ALLOCNO_HARD_REGNO (a) = -1; 4301 else 4302 { 4303 ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0); 4304 ira_overall_cost 4305 -= (ALLOCNO_MEMORY_COST (a) 4306 - (ALLOCNO_HARD_REG_COSTS (a) == NULL 4307 ? ALLOCNO_CLASS_COST (a) 4308 : ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index 4309 [aclass][hard_regno]])); 4310 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0 4311 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a), 4312 call_used_reg_set)) 4313 { 4314 ira_assert (flag_caller_saves); 4315 caller_save_needed = 1; 4316 } 4317 } 4318 4319 /* If we found a hard register, modify the RTL for the pseudo 4320 register to show the hard register, and mark the pseudo register 4321 live. */ 4322 if (reg_renumber[regno] >= 0) 4323 { 4324 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4325 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]); 4326 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]); 4327 mark_home_live (regno); 4328 } 4329 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4330 fprintf (ira_dump_file, "\n"); 4331 for (i = 0; i < n; i++) 4332 { 4333 ira_object_t obj = ALLOCNO_OBJECT (a, i); 4334 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]); 4335 } 4336 return reg_renumber[regno] >= 0; 4337} 4338 4339/* Sort pseudos according their usage frequencies (putting most 4340 frequently ones first). */ 4341static int 4342pseudo_reg_compare (const void *v1p, const void *v2p) 4343{ 4344 int regno1 = *(const int *) v1p; 4345 int regno2 = *(const int *) v2p; 4346 int diff; 4347 4348 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0) 4349 return diff; 4350 return regno1 - regno2; 4351} 4352 4353/* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are 4354 NUM of them) or spilled pseudos conflicting with pseudos in 4355 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the 4356 allocation has been changed. The function doesn't use 4357 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and 4358 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function 4359 is called by the reload pass at the end of each reload 4360 iteration. */ 4361bool 4362ira_reassign_pseudos (int *spilled_pseudo_regs, int num, 4363 HARD_REG_SET bad_spill_regs, 4364 HARD_REG_SET *pseudo_forbidden_regs, 4365 HARD_REG_SET *pseudo_previous_regs, 4366 bitmap spilled) 4367{ 4368 int i, n, regno; 4369 bool changed_p; 4370 ira_allocno_t a; 4371 HARD_REG_SET forbidden_regs; 4372 bitmap temp = BITMAP_ALLOC (NULL); 4373 4374 /* Add pseudos which conflict with pseudos already in 4375 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable 4376 to allocating in two steps as some of the conflicts might have 4377 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */ 4378 for (i = 0; i < num; i++) 4379 bitmap_set_bit (temp, spilled_pseudo_regs[i]); 4380 4381 for (i = 0, n = num; i < n; i++) 4382 { 4383 int nr, j; 4384 int regno = spilled_pseudo_regs[i]; 4385 bitmap_set_bit (temp, regno); 4386 4387 a = ira_regno_allocno_map[regno]; 4388 nr = ALLOCNO_NUM_OBJECTS (a); 4389 for (j = 0; j < nr; j++) 4390 { 4391 ira_object_t conflict_obj; 4392 ira_object_t obj = ALLOCNO_OBJECT (a, j); 4393 ira_object_conflict_iterator oci; 4394 4395 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 4396 { 4397 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 4398 if (ALLOCNO_HARD_REGNO (conflict_a) < 0 4399 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) 4400 && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a))) 4401 { 4402 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a); 4403 /* ?!? This seems wrong. */ 4404 bitmap_set_bit (consideration_allocno_bitmap, 4405 ALLOCNO_NUM (conflict_a)); 4406 } 4407 } 4408 } 4409 } 4410 4411 if (num > 1) 4412 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare); 4413 changed_p = false; 4414 /* Try to assign hard registers to pseudos from 4415 SPILLED_PSEUDO_REGS. */ 4416 for (i = 0; i < num; i++) 4417 { 4418 regno = spilled_pseudo_regs[i]; 4419 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); 4420 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]); 4421 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]); 4422 gcc_assert (reg_renumber[regno] < 0); 4423 a = ira_regno_allocno_map[regno]; 4424 ira_mark_allocation_change (regno); 4425 ira_assert (reg_renumber[regno] < 0); 4426 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 4427 fprintf (ira_dump_file, 4428 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), 4429 ALLOCNO_MEMORY_COST (a) 4430 - ALLOCNO_CLASS_COST (a)); 4431 allocno_reload_assign (a, forbidden_regs); 4432 if (reg_renumber[regno] >= 0) 4433 { 4434 CLEAR_REGNO_REG_SET (spilled, regno); 4435 changed_p = true; 4436 } 4437 } 4438 BITMAP_FREE (temp); 4439 return changed_p; 4440} 4441 4442/* The function is called by reload and returns already allocated 4443 stack slot (if any) for REGNO with given INHERENT_SIZE and 4444 TOTAL_SIZE. In the case of failure to find a slot which can be 4445 used for REGNO, the function returns NULL. */ 4446rtx 4447ira_reuse_stack_slot (int regno, unsigned int inherent_size, 4448 unsigned int total_size) 4449{ 4450 unsigned int i; 4451 int slot_num, best_slot_num; 4452 int cost, best_cost; 4453 ira_copy_t cp, next_cp; 4454 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno]; 4455 rtx x; 4456 bitmap_iterator bi; 4457 struct ira_spilled_reg_stack_slot *slot = NULL; 4458 4459 ira_assert (! ira_use_lra_p); 4460 4461 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno) 4462 && inherent_size <= total_size 4463 && ALLOCNO_HARD_REGNO (allocno) < 0); 4464 if (! flag_ira_share_spill_slots) 4465 return NULL_RTX; 4466 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2; 4467 if (slot_num != -1) 4468 { 4469 slot = &ira_spilled_reg_stack_slots[slot_num]; 4470 x = slot->mem; 4471 } 4472 else 4473 { 4474 best_cost = best_slot_num = -1; 4475 x = NULL_RTX; 4476 /* It means that the pseudo was spilled in the reload pass, try 4477 to reuse a slot. */ 4478 for (slot_num = 0; 4479 slot_num < ira_spilled_reg_stack_slots_num; 4480 slot_num++) 4481 { 4482 slot = &ira_spilled_reg_stack_slots[slot_num]; 4483 if (slot->mem == NULL_RTX) 4484 continue; 4485 if (slot->width < total_size 4486 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size) 4487 continue; 4488 4489 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, 4490 FIRST_PSEUDO_REGISTER, i, bi) 4491 { 4492 another_allocno = ira_regno_allocno_map[i]; 4493 if (allocnos_conflict_by_live_ranges_p (allocno, 4494 another_allocno)) 4495 goto cont; 4496 } 4497 for (cost = 0, cp = ALLOCNO_COPIES (allocno); 4498 cp != NULL; 4499 cp = next_cp) 4500 { 4501 if (cp->first == allocno) 4502 { 4503 next_cp = cp->next_first_allocno_copy; 4504 another_allocno = cp->second; 4505 } 4506 else if (cp->second == allocno) 4507 { 4508 next_cp = cp->next_second_allocno_copy; 4509 another_allocno = cp->first; 4510 } 4511 else 4512 gcc_unreachable (); 4513 if (cp->insn == NULL_RTX) 4514 continue; 4515 if (bitmap_bit_p (&slot->spilled_regs, 4516 ALLOCNO_REGNO (another_allocno))) 4517 cost += cp->freq; 4518 } 4519 if (cost > best_cost) 4520 { 4521 best_cost = cost; 4522 best_slot_num = slot_num; 4523 } 4524 cont: 4525 ; 4526 } 4527 if (best_cost >= 0) 4528 { 4529 slot_num = best_slot_num; 4530 slot = &ira_spilled_reg_stack_slots[slot_num]; 4531 SET_REGNO_REG_SET (&slot->spilled_regs, regno); 4532 x = slot->mem; 4533 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2; 4534 } 4535 } 4536 if (x != NULL_RTX) 4537 { 4538 ira_assert (slot->width >= total_size); 4539#ifdef ENABLE_IRA_CHECKING 4540 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, 4541 FIRST_PSEUDO_REGISTER, i, bi) 4542 { 4543 ira_assert (! conflict_by_live_ranges_p (regno, i)); 4544 } 4545#endif 4546 SET_REGNO_REG_SET (&slot->spilled_regs, regno); 4547 if (internal_flag_ira_verbose > 3 && ira_dump_file) 4548 { 4549 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of", 4550 regno, REG_FREQ (regno), slot_num); 4551 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, 4552 FIRST_PSEUDO_REGISTER, i, bi) 4553 { 4554 if ((unsigned) regno != i) 4555 fprintf (ira_dump_file, " %d", i); 4556 } 4557 fprintf (ira_dump_file, "\n"); 4558 } 4559 } 4560 return x; 4561} 4562 4563/* This is called by reload every time a new stack slot X with 4564 TOTAL_SIZE was allocated for REGNO. We store this info for 4565 subsequent ira_reuse_stack_slot calls. */ 4566void 4567ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size) 4568{ 4569 struct ira_spilled_reg_stack_slot *slot; 4570 int slot_num; 4571 ira_allocno_t allocno; 4572 4573 ira_assert (! ira_use_lra_p); 4574 4575 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size); 4576 allocno = ira_regno_allocno_map[regno]; 4577 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2; 4578 if (slot_num == -1) 4579 { 4580 slot_num = ira_spilled_reg_stack_slots_num++; 4581 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2; 4582 } 4583 slot = &ira_spilled_reg_stack_slots[slot_num]; 4584 INIT_REG_SET (&slot->spilled_regs); 4585 SET_REGNO_REG_SET (&slot->spilled_regs, regno); 4586 slot->mem = x; 4587 slot->width = total_size; 4588 if (internal_flag_ira_verbose > 3 && ira_dump_file) 4589 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n", 4590 regno, REG_FREQ (regno), slot_num); 4591} 4592 4593 4594/* Return spill cost for pseudo-registers whose numbers are in array 4595 REGNOS (with a negative number as an end marker) for reload with 4596 given IN and OUT for INSN. Return also number points (through 4597 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and 4598 the register pressure is high, number of references of the 4599 pseudo-registers (through NREFS), number of callee-clobbered 4600 hard-registers occupied by the pseudo-registers (through 4601 CALL_USED_COUNT), and the first hard regno occupied by the 4602 pseudo-registers (through FIRST_HARD_REGNO). */ 4603static int 4604calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn, 4605 int *excess_pressure_live_length, 4606 int *nrefs, int *call_used_count, int *first_hard_regno) 4607{ 4608 int i, cost, regno, hard_regno, j, count, saved_cost, nregs; 4609 bool in_p, out_p; 4610 int length; 4611 ira_allocno_t a; 4612 4613 *nrefs = 0; 4614 for (length = count = cost = i = 0;; i++) 4615 { 4616 regno = regnos[i]; 4617 if (regno < 0) 4618 break; 4619 *nrefs += REG_N_REFS (regno); 4620 hard_regno = reg_renumber[regno]; 4621 ira_assert (hard_regno >= 0); 4622 a = ira_regno_allocno_map[regno]; 4623 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a); 4624 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a); 4625 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)]; 4626 for (j = 0; j < nregs; j++) 4627 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)) 4628 break; 4629 if (j == nregs) 4630 count++; 4631 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno; 4632 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno; 4633 if ((in_p || out_p) 4634 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX) 4635 { 4636 saved_cost = 0; 4637 if (in_p) 4638 saved_cost += ira_memory_move_cost 4639 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1]; 4640 if (out_p) 4641 saved_cost 4642 += ira_memory_move_cost 4643 [ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0]; 4644 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost; 4645 } 4646 } 4647 *excess_pressure_live_length = length; 4648 *call_used_count = count; 4649 hard_regno = -1; 4650 if (regnos[0] >= 0) 4651 { 4652 hard_regno = reg_renumber[regnos[0]]; 4653 } 4654 *first_hard_regno = hard_regno; 4655 return cost; 4656} 4657 4658/* Return TRUE if spilling pseudo-registers whose numbers are in array 4659 REGNOS is better than spilling pseudo-registers with numbers in 4660 OTHER_REGNOS for reload with given IN and OUT for INSN. The 4661 function used by the reload pass to make better register spilling 4662 decisions. */ 4663bool 4664ira_better_spill_reload_regno_p (int *regnos, int *other_regnos, 4665 rtx in, rtx out, rtx insn) 4666{ 4667 int cost, other_cost; 4668 int length, other_length; 4669 int nrefs, other_nrefs; 4670 int call_used_count, other_call_used_count; 4671 int hard_regno, other_hard_regno; 4672 4673 cost = calculate_spill_cost (regnos, in, out, insn, 4674 &length, &nrefs, &call_used_count, &hard_regno); 4675 other_cost = calculate_spill_cost (other_regnos, in, out, insn, 4676 &other_length, &other_nrefs, 4677 &other_call_used_count, 4678 &other_hard_regno); 4679 if (nrefs == 0 && other_nrefs != 0) 4680 return true; 4681 if (nrefs != 0 && other_nrefs == 0) 4682 return false; 4683 if (cost != other_cost) 4684 return cost < other_cost; 4685 if (length != other_length) 4686 return length > other_length; 4687#ifdef REG_ALLOC_ORDER 4688 if (hard_regno >= 0 && other_hard_regno >= 0) 4689 return (inv_reg_alloc_order[hard_regno] 4690 < inv_reg_alloc_order[other_hard_regno]); 4691#else 4692 if (call_used_count != other_call_used_count) 4693 return call_used_count > other_call_used_count; 4694#endif 4695 return false; 4696} 4697 4698 4699 4700/* Allocate and initialize data necessary for assign_hard_reg. */ 4701void 4702ira_initiate_assign (void) 4703{ 4704 sorted_allocnos 4705 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) 4706 * ira_allocnos_num); 4707 consideration_allocno_bitmap = ira_allocate_bitmap (); 4708 initiate_cost_update (); 4709 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num); 4710 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num 4711 * sizeof (ira_copy_t)); 4712} 4713 4714/* Deallocate data used by assign_hard_reg. */ 4715void 4716ira_finish_assign (void) 4717{ 4718 ira_free (sorted_allocnos); 4719 ira_free_bitmap (consideration_allocno_bitmap); 4720 finish_cost_update (); 4721 ira_free (allocno_priorities); 4722 ira_free (sorted_copies); 4723} 4724 4725 4726 4727/* Entry function doing color-based register allocation. */ 4728static void 4729color (void) 4730{ 4731 allocno_stack_vec.create (ira_allocnos_num); 4732 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p)); 4733 ira_initiate_assign (); 4734 do_coloring (); 4735 ira_finish_assign (); 4736 allocno_stack_vec.release (); 4737 move_spill_restore (); 4738} 4739 4740 4741 4742/* This page contains a simple register allocator without usage of 4743 allocno conflicts. This is used for fast allocation for -O0. */ 4744 4745/* Do register allocation by not using allocno conflicts. It uses 4746 only allocno live ranges. The algorithm is close to Chow's 4747 priority coloring. */ 4748static void 4749fast_allocation (void) 4750{ 4751 int i, j, k, num, class_size, hard_regno; 4752#ifdef STACK_REGS 4753 bool no_stack_reg_p; 4754#endif 4755 enum reg_class aclass; 4756 machine_mode mode; 4757 ira_allocno_t a; 4758 ira_allocno_iterator ai; 4759 live_range_t r; 4760 HARD_REG_SET conflict_hard_regs, *used_hard_regs; 4761 4762 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) 4763 * ira_allocnos_num); 4764 num = 0; 4765 FOR_EACH_ALLOCNO (a, ai) 4766 sorted_allocnos[num++] = a; 4767 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num); 4768 setup_allocno_priorities (sorted_allocnos, num); 4769 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET) 4770 * ira_max_point); 4771 for (i = 0; i < ira_max_point; i++) 4772 CLEAR_HARD_REG_SET (used_hard_regs[i]); 4773 qsort (sorted_allocnos, num, sizeof (ira_allocno_t), 4774 allocno_priority_compare_func); 4775 for (i = 0; i < num; i++) 4776 { 4777 int nr, l; 4778 4779 a = sorted_allocnos[i]; 4780 nr = ALLOCNO_NUM_OBJECTS (a); 4781 CLEAR_HARD_REG_SET (conflict_hard_regs); 4782 for (l = 0; l < nr; l++) 4783 { 4784 ira_object_t obj = ALLOCNO_OBJECT (a, l); 4785 IOR_HARD_REG_SET (conflict_hard_regs, 4786 OBJECT_CONFLICT_HARD_REGS (obj)); 4787 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 4788 for (j = r->start; j <= r->finish; j++) 4789 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]); 4790 } 4791 aclass = ALLOCNO_CLASS (a); 4792 ALLOCNO_ASSIGNED_P (a) = true; 4793 ALLOCNO_HARD_REGNO (a) = -1; 4794 if (hard_reg_set_subset_p (reg_class_contents[aclass], 4795 conflict_hard_regs)) 4796 continue; 4797 mode = ALLOCNO_MODE (a); 4798#ifdef STACK_REGS 4799 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a); 4800#endif 4801 class_size = ira_class_hard_regs_num[aclass]; 4802 for (j = 0; j < class_size; j++) 4803 { 4804 hard_regno = ira_class_hard_regs[aclass][j]; 4805#ifdef STACK_REGS 4806 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno 4807 && hard_regno <= LAST_STACK_REG) 4808 continue; 4809#endif 4810 if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs) 4811 || (TEST_HARD_REG_BIT 4812 (ira_prohibited_class_mode_regs[aclass][mode], hard_regno))) 4813 continue; 4814 ALLOCNO_HARD_REGNO (a) = hard_regno; 4815 for (l = 0; l < nr; l++) 4816 { 4817 ira_object_t obj = ALLOCNO_OBJECT (a, l); 4818 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 4819 for (k = r->start; k <= r->finish; k++) 4820 IOR_HARD_REG_SET (used_hard_regs[k], 4821 ira_reg_mode_hard_regset[hard_regno][mode]); 4822 } 4823 break; 4824 } 4825 } 4826 ira_free (sorted_allocnos); 4827 ira_free (used_hard_regs); 4828 ira_free (allocno_priorities); 4829 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 4830 ira_print_disposition (ira_dump_file); 4831} 4832 4833 4834 4835/* Entry function doing coloring. */ 4836void 4837ira_color (void) 4838{ 4839 ira_allocno_t a; 4840 ira_allocno_iterator ai; 4841 4842 /* Setup updated costs. */ 4843 FOR_EACH_ALLOCNO (a, ai) 4844 { 4845 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a); 4846 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a); 4847 } 4848 if (ira_conflicts_p) 4849 color (); 4850 else 4851 fast_allocation (); 4852} 4853