1 /* Assign reload pseudos. 2 Copyright (C) 2010-2013 Free Software Foundation, Inc. 3 Contributed by Vladimir Makarov <vmakarov@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 22 /* This file's main objective is to assign hard registers to reload 23 pseudos. It also tries to allocate hard registers to other 24 pseudos, but at a lower priority than the reload pseudos. The pass 25 does not transform the RTL. 26 27 We must allocate a hard register to every reload pseudo. We try to 28 increase the chances of finding a viable allocation by assigning 29 the pseudos in order of fewest available hard registers first. If 30 we still fail to find a hard register, we spill other (non-reload) 31 pseudos in order to make room. 32 33 find_hard_regno_for finds hard registers for allocation without 34 spilling. spill_for does the same with spilling. Both functions 35 use a cost model to determine the most profitable choice of hard 36 and spill registers. 37 38 Once we have finished allocating reload pseudos, we also try to 39 assign registers to other (non-reload) pseudos. This is useful if 40 hard registers were freed up by the spilling just described. 41 42 We try to assign hard registers by collecting pseudos into threads. 43 These threads contain reload and inheritance pseudos that are 44 connected by copies (move insns). Doing this improves the chances 45 of pseudos in the thread getting the same hard register and, as a 46 result, of allowing some move insns to be deleted. 47 48 When we assign a hard register to a pseudo, we decrease the cost of 49 using the same hard register for pseudos that are connected by 50 copies. 51 52 If two hard registers have the same frequency-derived cost, we 53 prefer hard registers with higher priorities. The mapping of 54 registers to priorities is controlled by the register_priority 55 target hook. For example, x86-64 has a few register priorities: 56 hard registers with and without REX prefixes have different 57 priorities. This permits us to generate smaller code as insns 58 without REX prefixes are shorter. 59 60 If a few hard registers are still equally good for the assignment, 61 we choose the least used hard register. It is called leveling and 62 may be profitable for some targets. 63 64 Only insns with changed allocation pseudos are processed on the 65 next constraint pass. 66 67 The pseudo live-ranges are used to find conflicting pseudos. 68 69 For understanding the code, it is important to keep in mind that 70 inheritance, split, and reload pseudos created since last 71 constraint pass have regno >= lra_constraint_new_regno_start. 72 Inheritance and split pseudos created on any pass are in the 73 corresponding bitmaps. Inheritance and split pseudos since the 74 last constraint pass have also the corresponding non-negative 75 restore_regno. */ 76 77 #include "config.h" 78 #include "system.h" 79 #include "coretypes.h" 80 #include "tm.h" 81 #include "hard-reg-set.h" 82 #include "rtl.h" 83 #include "rtl-error.h" 84 #include "tm_p.h" 85 #include "target.h" 86 #include "insn-config.h" 87 #include "recog.h" 88 #include "output.h" 89 #include "regs.h" 90 #include "function.h" 91 #include "expr.h" 92 #include "basic-block.h" 93 #include "except.h" 94 #include "df.h" 95 #include "ira.h" 96 #include "sparseset.h" 97 #include "lra-int.h" 98 99 /* Array containing corresponding values of function 100 lra_get_allocno_class. It is used to speed up the code. */ 101 static enum reg_class *regno_allocno_class_array; 102 103 /* Information about the thread to which a pseudo belongs. Threads are 104 a set of connected reload and inheritance pseudos with the same set of 105 available hard registers. Lone registers belong to their own threads. */ 106 struct regno_assign_info 107 { 108 /* First/next pseudo of the same thread. */ 109 int first, next; 110 /* Frequency of the thread (execution frequency of only reload 111 pseudos in the thread when the thread contains a reload pseudo). 112 Defined only for the first thread pseudo. */ 113 int freq; 114 }; 115 116 /* Map regno to the corresponding regno assignment info. */ 117 static struct regno_assign_info *regno_assign_info; 118 119 /* All inherited, subreg or optional pseudos created before last spill 120 sub-pass. Such pseudos are permitted to get memory instead of hard 121 regs. */ 122 static bitmap_head non_reload_pseudos; 123 124 /* Process a pseudo copy with execution frequency COPY_FREQ connecting 125 REGNO1 and REGNO2 to form threads. */ 126 static void 127 process_copy_to_form_thread (int regno1, int regno2, int copy_freq) 128 { 129 int last, regno1_first, regno2_first; 130 131 lra_assert (regno1 >= lra_constraint_new_regno_start 132 && regno2 >= lra_constraint_new_regno_start); 133 regno1_first = regno_assign_info[regno1].first; 134 regno2_first = regno_assign_info[regno2].first; 135 if (regno1_first != regno2_first) 136 { 137 for (last = regno2_first; 138 regno_assign_info[last].next >= 0; 139 last = regno_assign_info[last].next) 140 regno_assign_info[last].first = regno1_first; 141 regno_assign_info[last].first = regno1_first; 142 regno_assign_info[last].next = regno_assign_info[regno1_first].next; 143 regno_assign_info[regno1_first].next = regno2_first; 144 regno_assign_info[regno1_first].freq 145 += regno_assign_info[regno2_first].freq; 146 } 147 regno_assign_info[regno1_first].freq -= 2 * copy_freq; 148 lra_assert (regno_assign_info[regno1_first].freq >= 0); 149 } 150 151 /* Initialize REGNO_ASSIGN_INFO and form threads. */ 152 static void 153 init_regno_assign_info (void) 154 { 155 int i, regno1, regno2, max_regno = max_reg_num (); 156 lra_copy_t cp; 157 158 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno); 159 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 160 { 161 regno_assign_info[i].first = i; 162 regno_assign_info[i].next = -1; 163 regno_assign_info[i].freq = lra_reg_info[i].freq; 164 } 165 /* Form the threads. */ 166 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++) 167 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start 168 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start 169 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0 170 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0 171 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]] 172 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]])) 173 process_copy_to_form_thread (regno1, regno2, cp->freq); 174 } 175 176 /* Free REGNO_ASSIGN_INFO. */ 177 static void 178 finish_regno_assign_info (void) 179 { 180 free (regno_assign_info); 181 } 182 183 /* The function is used to sort *reload* and *inheritance* pseudos to 184 try to assign them hard registers. We put pseudos from the same 185 thread always nearby. */ 186 static int 187 reload_pseudo_compare_func (const void *v1p, const void *v2p) 188 { 189 int r1 = *(const int *) v1p, r2 = *(const int *) v2p; 190 enum reg_class cl1 = regno_allocno_class_array[r1]; 191 enum reg_class cl2 = regno_allocno_class_array[r2]; 192 int diff; 193 194 lra_assert (r1 >= lra_constraint_new_regno_start 195 && r2 >= lra_constraint_new_regno_start); 196 197 /* Prefer to assign reload registers with smaller classes first to 198 guarantee assignment to all reload registers. */ 199 if ((diff = (ira_class_hard_regs_num[cl1] 200 - ira_class_hard_regs_num[cl2])) != 0) 201 return diff; 202 if ((diff 203 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode] 204 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0 205 /* The code below executes rarely as nregs == 1 in most cases. 206 So we should not worry about using faster data structures to 207 check reload pseudos. */ 208 && ! bitmap_bit_p (&non_reload_pseudos, r1) 209 && ! bitmap_bit_p (&non_reload_pseudos, r2)) 210 return diff; 211 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq 212 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0) 213 return diff; 214 /* Allocate bigger pseudos first to avoid register file 215 fragmentation. */ 216 if ((diff 217 = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode] 218 - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0) 219 return diff; 220 /* Put pseudos from the thread nearby. */ 221 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0) 222 return diff; 223 /* If regs are equally good, sort by their numbers, so that the 224 results of qsort leave nothing to chance. */ 225 return r1 - r2; 226 } 227 228 /* The function is used to sort *non-reload* pseudos to try to assign 229 them hard registers. The order calculation is simpler than in the 230 previous function and based on the pseudo frequency usage. */ 231 static int 232 pseudo_compare_func (const void *v1p, const void *v2p) 233 { 234 int r1 = *(const int *) v1p, r2 = *(const int *) v2p; 235 int diff; 236 237 /* Prefer to assign more frequently used registers first. */ 238 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0) 239 return diff; 240 241 /* If regs are equally good, sort by their numbers, so that the 242 results of qsort leave nothing to chance. */ 243 return r1 - r2; 244 } 245 246 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the 247 pseudo live ranges with given start point. We insert only live 248 ranges of pseudos interesting for assignment purposes. They are 249 reload pseudos and pseudos assigned to hard registers. */ 250 static lra_live_range_t *start_point_ranges; 251 252 /* Used as a flag that a live range is not inserted in the start point 253 chain. */ 254 static struct lra_live_range not_in_chain_mark; 255 256 /* Create and set up START_POINT_RANGES. */ 257 static void 258 create_live_range_start_chains (void) 259 { 260 int i, max_regno; 261 lra_live_range_t r; 262 263 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point); 264 max_regno = max_reg_num (); 265 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 266 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0) 267 { 268 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 269 { 270 r->start_next = start_point_ranges[r->start]; 271 start_point_ranges[r->start] = r; 272 } 273 } 274 else 275 { 276 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 277 r->start_next = ¬_in_chain_mark; 278 } 279 } 280 281 /* Insert live ranges of pseudo REGNO into start chains if they are 282 not there yet. */ 283 static void 284 insert_in_live_range_start_chain (int regno) 285 { 286 lra_live_range_t r = lra_reg_info[regno].live_ranges; 287 288 if (r->start_next != ¬_in_chain_mark) 289 return; 290 for (; r != NULL; r = r->next) 291 { 292 r->start_next = start_point_ranges[r->start]; 293 start_point_ranges[r->start] = r; 294 } 295 } 296 297 /* Free START_POINT_RANGES. */ 298 static void 299 finish_live_range_start_chains (void) 300 { 301 gcc_assert (start_point_ranges != NULL); 302 free (start_point_ranges); 303 start_point_ranges = NULL; 304 } 305 306 /* Map: program point -> bitmap of all pseudos living at the point and 307 assigned to hard registers. */ 308 static bitmap_head *live_hard_reg_pseudos; 309 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack; 310 311 /* reg_renumber corresponding to pseudos marked in 312 live_hard_reg_pseudos. reg_renumber might be not matched to 313 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects 314 live_hard_reg_pseudos. */ 315 static int *live_pseudos_reg_renumber; 316 317 /* Sparseset used to calculate living hard reg pseudos for some program 318 point range. */ 319 static sparseset live_range_hard_reg_pseudos; 320 321 /* Sparseset used to calculate living reload/inheritance pseudos for 322 some program point range. */ 323 static sparseset live_range_reload_inheritance_pseudos; 324 325 /* Allocate and initialize the data about living pseudos at program 326 points. */ 327 static void 328 init_lives (void) 329 { 330 int i, max_regno = max_reg_num (); 331 332 live_range_hard_reg_pseudos = sparseset_alloc (max_regno); 333 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno); 334 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point); 335 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack); 336 for (i = 0; i < lra_live_max_point; i++) 337 bitmap_initialize (&live_hard_reg_pseudos[i], 338 &live_hard_reg_pseudos_bitmap_obstack); 339 live_pseudos_reg_renumber = XNEWVEC (int, max_regno); 340 for (i = 0; i < max_regno; i++) 341 live_pseudos_reg_renumber[i] = -1; 342 } 343 344 /* Free the data about living pseudos at program points. */ 345 static void 346 finish_lives (void) 347 { 348 sparseset_free (live_range_hard_reg_pseudos); 349 sparseset_free (live_range_reload_inheritance_pseudos); 350 free (live_hard_reg_pseudos); 351 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack); 352 free (live_pseudos_reg_renumber); 353 } 354 355 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER 356 entries for pseudo REGNO. Assume that the register has been 357 spilled if FREE_P, otherwise assume that it has been assigned 358 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live 359 ranges in the start chains when it is assumed to be assigned to a 360 hard register because we use the chains of pseudos assigned to hard 361 registers during allocation. */ 362 static void 363 update_lives (int regno, bool free_p) 364 { 365 int p; 366 lra_live_range_t r; 367 368 if (reg_renumber[regno] < 0) 369 return; 370 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno]; 371 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 372 { 373 for (p = r->start; p <= r->finish; p++) 374 if (free_p) 375 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno); 376 else 377 { 378 bitmap_set_bit (&live_hard_reg_pseudos[p], regno); 379 insert_in_live_range_start_chain (regno); 380 } 381 } 382 } 383 384 /* Sparseset used to calculate reload pseudos conflicting with a given 385 pseudo when we are trying to find a hard register for the given 386 pseudo. */ 387 static sparseset conflict_reload_and_inheritance_pseudos; 388 389 /* Map: program point -> bitmap of all reload and inheritance pseudos 390 living at the point. */ 391 static bitmap_head *live_reload_and_inheritance_pseudos; 392 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack; 393 394 /* Allocate and initialize data about living reload pseudos at any 395 given program point. */ 396 static void 397 init_live_reload_and_inheritance_pseudos (void) 398 { 399 int i, p, max_regno = max_reg_num (); 400 lra_live_range_t r; 401 402 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno); 403 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point); 404 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack); 405 for (p = 0; p < lra_live_max_point; p++) 406 bitmap_initialize (&live_reload_and_inheritance_pseudos[p], 407 &live_reload_and_inheritance_pseudos_bitmap_obstack); 408 for (i = lra_constraint_new_regno_start; i < max_regno; i++) 409 { 410 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 411 for (p = r->start; p <= r->finish; p++) 412 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i); 413 } 414 } 415 416 /* Finalize data about living reload pseudos at any given program 417 point. */ 418 static void 419 finish_live_reload_and_inheritance_pseudos (void) 420 { 421 sparseset_free (conflict_reload_and_inheritance_pseudos); 422 free (live_reload_and_inheritance_pseudos); 423 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack); 424 } 425 426 /* The value used to check that cost of given hard reg is really 427 defined currently. */ 428 static int curr_hard_regno_costs_check = 0; 429 /* Array used to check that cost of the corresponding hard reg (the 430 array element index) is really defined currently. */ 431 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER]; 432 /* The current costs of allocation of hard regs. Defined only if the 433 value of the corresponding element of the previous array is equal to 434 CURR_HARD_REGNO_COSTS_CHECK. */ 435 static int hard_regno_costs[FIRST_PSEUDO_REGISTER]; 436 437 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is 438 not defined yet. */ 439 static inline void 440 adjust_hard_regno_cost (int hard_regno, int incr) 441 { 442 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check) 443 hard_regno_costs[hard_regno] = 0; 444 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check; 445 hard_regno_costs[hard_regno] += incr; 446 } 447 448 /* Try to find a free hard register for pseudo REGNO. Return the 449 hard register on success and set *COST to the cost of using 450 that register. (If several registers have equal cost, the one with 451 the highest priority wins.) Return -1 on failure. 452 453 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register, 454 otherwise consider all hard registers in REGNO's class. */ 455 static int 456 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno) 457 { 458 HARD_REG_SET conflict_set; 459 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX; 460 lra_live_range_t r; 461 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno; 462 int hr, conflict_hr, nregs; 463 enum machine_mode biggest_mode; 464 unsigned int k, conflict_regno; 465 int val, biggest_nregs, nregs_diff; 466 enum reg_class rclass; 467 bitmap_iterator bi; 468 bool *rclass_intersect_p; 469 HARD_REG_SET impossible_start_hard_regs; 470 471 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs); 472 rclass = regno_allocno_class_array[regno]; 473 rclass_intersect_p = ira_reg_classes_intersect_p[rclass]; 474 curr_hard_regno_costs_check++; 475 sparseset_clear (conflict_reload_and_inheritance_pseudos); 476 sparseset_clear (live_range_hard_reg_pseudos); 477 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs); 478 biggest_mode = lra_reg_info[regno].biggest_mode; 479 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 480 { 481 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi) 482 if (rclass_intersect_p[regno_allocno_class_array[k]]) 483 sparseset_set_bit (live_range_hard_reg_pseudos, k); 484 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start], 485 0, k, bi) 486 if (lra_reg_info[k].preferred_hard_regno1 >= 0 487 && live_pseudos_reg_renumber[k] < 0 488 && rclass_intersect_p[regno_allocno_class_array[k]]) 489 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k); 490 for (p = r->start + 1; p <= r->finish; p++) 491 { 492 lra_live_range_t r2; 493 494 for (r2 = start_point_ranges[p]; 495 r2 != NULL; 496 r2 = r2->start_next) 497 { 498 if (r2->regno >= lra_constraint_new_regno_start 499 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0 500 && live_pseudos_reg_renumber[r2->regno] < 0 501 && rclass_intersect_p[regno_allocno_class_array[r2->regno]]) 502 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, 503 r2->regno); 504 if (live_pseudos_reg_renumber[r2->regno] >= 0 505 && rclass_intersect_p[regno_allocno_class_array[r2->regno]]) 506 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno); 507 } 508 } 509 } 510 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0) 511 { 512 adjust_hard_regno_cost 513 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1); 514 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0) 515 adjust_hard_regno_cost 516 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2); 517 } 518 #ifdef STACK_REGS 519 if (lra_reg_info[regno].no_stack_p) 520 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) 521 SET_HARD_REG_BIT (conflict_set, i); 522 #endif 523 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno); 524 val = lra_reg_info[regno].val; 525 CLEAR_HARD_REG_SET (impossible_start_hard_regs); 526 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno) 527 if (val == lra_reg_info[conflict_regno].val) 528 { 529 conflict_hr = live_pseudos_reg_renumber[conflict_regno]; 530 nregs = (hard_regno_nregs[conflict_hr] 531 [lra_reg_info[conflict_regno].biggest_mode]); 532 /* Remember about multi-register pseudos. For example, 2 hard 533 register pseudos can start on the same hard register but can 534 not start on HR and HR+1/HR-1. */ 535 for (hr = conflict_hr + 1; 536 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs; 537 hr++) 538 SET_HARD_REG_BIT (impossible_start_hard_regs, hr); 539 for (hr = conflict_hr - 1; 540 hr >= 0 && hr + hard_regno_nregs[hr][biggest_mode] > conflict_hr; 541 hr--) 542 SET_HARD_REG_BIT (impossible_start_hard_regs, hr); 543 } 544 else 545 { 546 add_to_hard_reg_set (&conflict_set, 547 lra_reg_info[conflict_regno].biggest_mode, 548 live_pseudos_reg_renumber[conflict_regno]); 549 if (hard_reg_set_subset_p (reg_class_contents[rclass], 550 conflict_set)) 551 return -1; 552 } 553 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos, 554 conflict_regno) 555 if (val != lra_reg_info[conflict_regno].val) 556 { 557 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0); 558 if ((hard_regno 559 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0) 560 { 561 adjust_hard_regno_cost 562 (hard_regno, 563 lra_reg_info[conflict_regno].preferred_hard_regno_profit1); 564 if ((hard_regno 565 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0) 566 adjust_hard_regno_cost 567 (hard_regno, 568 lra_reg_info[conflict_regno].preferred_hard_regno_profit2); 569 } 570 } 571 /* Make sure that all registers in a multi-word pseudo belong to the 572 required class. */ 573 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]); 574 lra_assert (rclass != NO_REGS); 575 rclass_size = ira_class_hard_regs_num[rclass]; 576 best_hard_regno = -1; 577 hard_regno = ira_class_hard_regs[rclass][0]; 578 biggest_nregs = hard_regno_nregs[hard_regno][biggest_mode]; 579 nregs_diff = (biggest_nregs 580 - hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]); 581 for (i = 0; i < rclass_size; i++) 582 { 583 if (try_only_hard_regno >= 0) 584 hard_regno = try_only_hard_regno; 585 else 586 hard_regno = ira_class_hard_regs[rclass][i]; 587 if (! overlaps_hard_reg_set_p (conflict_set, 588 PSEUDO_REGNO_MODE (regno), hard_regno) 589 /* We can not use prohibited_class_mode_regs because it is 590 not defined for all classes. */ 591 && HARD_REGNO_MODE_OK (hard_regno, PSEUDO_REGNO_MODE (regno)) 592 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno) 593 && (nregs_diff == 0 594 || (WORDS_BIG_ENDIAN 595 ? (hard_regno - nregs_diff >= 0 596 && TEST_HARD_REG_BIT (reg_class_contents[rclass], 597 hard_regno - nregs_diff)) 598 : TEST_HARD_REG_BIT (reg_class_contents[rclass], 599 hard_regno + nregs_diff)))) 600 { 601 if (hard_regno_costs_check[hard_regno] 602 != curr_hard_regno_costs_check) 603 { 604 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check; 605 hard_regno_costs[hard_regno] = 0; 606 } 607 for (j = 0; 608 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]; 609 j++) 610 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j) 611 && ! df_regs_ever_live_p (hard_regno + j)) 612 /* It needs save restore. */ 613 hard_regno_costs[hard_regno] 614 += 2 * ENTRY_BLOCK_PTR->next_bb->frequency; 615 priority = targetm.register_priority (hard_regno); 616 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost 617 || (hard_regno_costs[hard_regno] == best_cost 618 && (priority > best_priority 619 /* Hard register usage leveling actually results 620 in bigger code for targets with conditional 621 execution like ARM because it reduces chance 622 of if-conversion after LRA. */ 623 || (! targetm.have_conditional_execution () 624 && priority == best_priority 625 && best_usage > lra_hard_reg_usage[hard_regno])))) 626 { 627 best_hard_regno = hard_regno; 628 best_cost = hard_regno_costs[hard_regno]; 629 best_priority = priority; 630 best_usage = lra_hard_reg_usage[hard_regno]; 631 } 632 } 633 if (try_only_hard_regno >= 0) 634 break; 635 } 636 if (best_hard_regno >= 0) 637 *cost = best_cost - lra_reg_info[regno].freq; 638 return best_hard_regno; 639 } 640 641 /* Current value used for checking elements in 642 update_hard_regno_preference_check. */ 643 static int curr_update_hard_regno_preference_check; 644 /* If an element value is equal to the above variable value, then the 645 corresponding regno has been processed for preference 646 propagation. */ 647 static int *update_hard_regno_preference_check; 648 649 /* Update the preference for using HARD_REGNO for pseudos that are 650 connected directly or indirectly with REGNO. Apply divisor DIV 651 to any preference adjustments. 652 653 The more indirectly a pseudo is connected, the smaller its effect 654 should be. We therefore increase DIV on each "hop". */ 655 static void 656 update_hard_regno_preference (int regno, int hard_regno, int div) 657 { 658 int another_regno, cost; 659 lra_copy_t cp, next_cp; 660 661 /* Search depth 5 seems to be enough. */ 662 if (div > (1 << 5)) 663 return; 664 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp) 665 { 666 if (cp->regno1 == regno) 667 { 668 next_cp = cp->regno1_next; 669 another_regno = cp->regno2; 670 } 671 else if (cp->regno2 == regno) 672 { 673 next_cp = cp->regno2_next; 674 another_regno = cp->regno1; 675 } 676 else 677 gcc_unreachable (); 678 if (reg_renumber[another_regno] < 0 679 && (update_hard_regno_preference_check[another_regno] 680 != curr_update_hard_regno_preference_check)) 681 { 682 update_hard_regno_preference_check[another_regno] 683 = curr_update_hard_regno_preference_check; 684 cost = cp->freq < div ? 1 : cp->freq / div; 685 lra_setup_reload_pseudo_preferenced_hard_reg 686 (another_regno, hard_regno, cost); 687 update_hard_regno_preference (another_regno, hard_regno, div * 2); 688 } 689 } 690 } 691 692 /* Update REG_RENUMBER and other pseudo preferences by assignment of 693 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */ 694 void 695 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p) 696 { 697 int i, hr; 698 699 /* We can not just reassign hard register. */ 700 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0); 701 if ((hr = hard_regno) < 0) 702 hr = reg_renumber[regno]; 703 reg_renumber[regno] = hard_regno; 704 lra_assert (hr >= 0); 705 for (i = 0; i < hard_regno_nregs[hr][PSEUDO_REGNO_MODE (regno)]; i++) 706 if (hard_regno < 0) 707 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq; 708 else 709 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq; 710 if (print_p && lra_dump_file != NULL) 711 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n", 712 reg_renumber[regno], 713 regno < lra_constraint_new_regno_start 714 ? "" 715 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance " 716 : bitmap_bit_p (&lra_split_regs, regno) ? "split " 717 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) 718 ? "optional reload ": "reload ", 719 regno, lra_reg_info[regno].freq); 720 if (hard_regno >= 0) 721 { 722 curr_update_hard_regno_preference_check++; 723 update_hard_regno_preference (regno, hard_regno, 1); 724 } 725 } 726 727 /* Pseudos which occur in insns containing a particular pseudo. */ 728 static bitmap_head insn_conflict_pseudos; 729 730 /* Bitmaps used to contain spill pseudos for given pseudo hard regno 731 and best spill pseudos for given pseudo (and best hard regno). */ 732 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap; 733 734 /* Current pseudo check for validity of elements in 735 TRY_HARD_REG_PSEUDOS. */ 736 static int curr_pseudo_check; 737 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */ 738 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER]; 739 /* Pseudos who hold given hard register at the considered points. */ 740 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER]; 741 742 /* Set up try_hard_reg_pseudos for given program point P and class 743 RCLASS. Those are pseudos living at P and assigned to a hard 744 register of RCLASS. In other words, those are pseudos which can be 745 spilled to assign a hard register of RCLASS to a pseudo living at 746 P. */ 747 static void 748 setup_try_hard_regno_pseudos (int p, enum reg_class rclass) 749 { 750 int i, hard_regno; 751 enum machine_mode mode; 752 unsigned int spill_regno; 753 bitmap_iterator bi; 754 755 /* Find what pseudos could be spilled. */ 756 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi) 757 { 758 mode = PSEUDO_REGNO_MODE (spill_regno); 759 hard_regno = live_pseudos_reg_renumber[spill_regno]; 760 if (overlaps_hard_reg_set_p (reg_class_contents[rclass], 761 mode, hard_regno)) 762 { 763 for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--) 764 { 765 if (try_hard_reg_pseudos_check[hard_regno + i] 766 != curr_pseudo_check) 767 { 768 try_hard_reg_pseudos_check[hard_regno + i] 769 = curr_pseudo_check; 770 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]); 771 } 772 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i], 773 spill_regno); 774 } 775 } 776 } 777 } 778 779 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary 780 assignment means that we might undo the data change. */ 781 static void 782 assign_temporarily (int regno, int hard_regno) 783 { 784 int p; 785 lra_live_range_t r; 786 787 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 788 { 789 for (p = r->start; p <= r->finish; p++) 790 if (hard_regno < 0) 791 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno); 792 else 793 { 794 bitmap_set_bit (&live_hard_reg_pseudos[p], regno); 795 insert_in_live_range_start_chain (regno); 796 } 797 } 798 live_pseudos_reg_renumber[regno] = hard_regno; 799 } 800 801 /* Array used for sorting reload pseudos for subsequent allocation 802 after spilling some pseudo. */ 803 static int *sorted_reload_pseudos; 804 805 /* Spill some pseudos for a reload pseudo REGNO and return hard 806 register which should be used for pseudo after spilling. The 807 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we 808 choose hard register (and pseudos occupying the hard registers and 809 to be spilled), we take into account not only how REGNO will 810 benefit from the spills but also how other reload pseudos not yet 811 assigned to hard registers benefit from the spills too. In very 812 rare cases, the function can fail and return -1. */ 813 static int 814 spill_for (int regno, bitmap spilled_pseudo_bitmap) 815 { 816 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size; 817 int reload_hard_regno, reload_cost; 818 enum machine_mode mode; 819 enum reg_class rclass; 820 unsigned int spill_regno, reload_regno, uid; 821 int insn_pseudos_num, best_insn_pseudos_num; 822 lra_live_range_t r; 823 bitmap_iterator bi; 824 825 rclass = regno_allocno_class_array[regno]; 826 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS); 827 bitmap_clear (&insn_conflict_pseudos); 828 bitmap_clear (&best_spill_pseudos_bitmap); 829 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi) 830 { 831 struct lra_insn_reg *ir; 832 833 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next) 834 if (ir->regno >= FIRST_PSEUDO_REGISTER) 835 bitmap_set_bit (&insn_conflict_pseudos, ir->regno); 836 } 837 best_hard_regno = -1; 838 best_cost = INT_MAX; 839 best_insn_pseudos_num = INT_MAX; 840 rclass_size = ira_class_hard_regs_num[rclass]; 841 mode = PSEUDO_REGNO_MODE (regno); 842 /* Invalidate try_hard_reg_pseudos elements. */ 843 curr_pseudo_check++; 844 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 845 for (p = r->start; p <= r->finish; p++) 846 setup_try_hard_regno_pseudos (p, rclass); 847 for (i = 0; i < rclass_size; i++) 848 { 849 hard_regno = ira_class_hard_regs[rclass][i]; 850 bitmap_clear (&spill_pseudos_bitmap); 851 for (j = hard_regno_nregs[hard_regno][mode] - 1; j >= 0; j--) 852 { 853 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check) 854 continue; 855 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j])); 856 bitmap_ior_into (&spill_pseudos_bitmap, 857 &try_hard_reg_pseudos[hard_regno + j]); 858 } 859 /* Spill pseudos. */ 860 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 861 if ((int) spill_regno >= lra_constraint_new_regno_start 862 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno) 863 && ! bitmap_bit_p (&lra_split_regs, spill_regno) 864 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)) 865 goto fail; 866 insn_pseudos_num = 0; 867 if (lra_dump_file != NULL) 868 fprintf (lra_dump_file, " Trying %d:", hard_regno); 869 sparseset_clear (live_range_reload_inheritance_pseudos); 870 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 871 { 872 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno)) 873 insn_pseudos_num++; 874 for (r = lra_reg_info[spill_regno].live_ranges; 875 r != NULL; 876 r = r->next) 877 { 878 for (p = r->start; p <= r->finish; p++) 879 { 880 lra_live_range_t r2; 881 882 for (r2 = start_point_ranges[p]; 883 r2 != NULL; 884 r2 = r2->start_next) 885 if (r2->regno >= lra_constraint_new_regno_start) 886 sparseset_set_bit (live_range_reload_inheritance_pseudos, 887 r2->regno); 888 } 889 } 890 } 891 n = 0; 892 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos, 893 reload_regno) 894 if ((int) reload_regno != regno 895 && (ira_reg_classes_intersect_p 896 [rclass][regno_allocno_class_array[reload_regno]]) 897 && live_pseudos_reg_renumber[reload_regno] < 0 898 && find_hard_regno_for (reload_regno, &cost, -1) < 0) 899 sorted_reload_pseudos[n++] = reload_regno; 900 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 901 { 902 update_lives (spill_regno, true); 903 if (lra_dump_file != NULL) 904 fprintf (lra_dump_file, " spill %d(freq=%d)", 905 spill_regno, lra_reg_info[spill_regno].freq); 906 } 907 hard_regno = find_hard_regno_for (regno, &cost, -1); 908 if (hard_regno >= 0) 909 { 910 assign_temporarily (regno, hard_regno); 911 qsort (sorted_reload_pseudos, n, sizeof (int), 912 reload_pseudo_compare_func); 913 for (j = 0; j < n; j++) 914 { 915 reload_regno = sorted_reload_pseudos[j]; 916 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0); 917 if ((reload_hard_regno 918 = find_hard_regno_for (reload_regno, 919 &reload_cost, -1)) >= 0) 920 { 921 if (lra_dump_file != NULL) 922 fprintf (lra_dump_file, " assign %d(cost=%d)", 923 reload_regno, reload_cost); 924 assign_temporarily (reload_regno, reload_hard_regno); 925 cost += reload_cost; 926 } 927 } 928 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 929 { 930 rtx x; 931 932 cost += lra_reg_info[spill_regno].freq; 933 if (ira_reg_equiv[spill_regno].memory != NULL 934 || ira_reg_equiv[spill_regno].constant != NULL) 935 for (x = ira_reg_equiv[spill_regno].init_insns; 936 x != NULL; 937 x = XEXP (x, 1)) 938 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (XEXP (x, 0))); 939 } 940 if (best_insn_pseudos_num > insn_pseudos_num 941 || (best_insn_pseudos_num == insn_pseudos_num 942 && best_cost > cost)) 943 { 944 best_insn_pseudos_num = insn_pseudos_num; 945 best_cost = cost; 946 best_hard_regno = hard_regno; 947 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap); 948 if (lra_dump_file != NULL) 949 fprintf (lra_dump_file, " Now best %d(cost=%d)\n", 950 hard_regno, cost); 951 } 952 assign_temporarily (regno, -1); 953 for (j = 0; j < n; j++) 954 { 955 reload_regno = sorted_reload_pseudos[j]; 956 if (live_pseudos_reg_renumber[reload_regno] >= 0) 957 assign_temporarily (reload_regno, -1); 958 } 959 } 960 if (lra_dump_file != NULL) 961 fprintf (lra_dump_file, "\n"); 962 /* Restore the live hard reg pseudo info for spilled pseudos. */ 963 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 964 update_lives (spill_regno, false); 965 fail: 966 ; 967 } 968 /* Spill: */ 969 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi) 970 { 971 if (lra_dump_file != NULL) 972 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n", 973 ((int) spill_regno < lra_constraint_new_regno_start 974 ? "" 975 : bitmap_bit_p (&lra_inheritance_pseudos, spill_regno) 976 ? "inheritance " 977 : bitmap_bit_p (&lra_split_regs, spill_regno) 978 ? "split " 979 : bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno) 980 ? "optional reload " : "reload "), 981 spill_regno, reg_renumber[spill_regno], 982 lra_reg_info[spill_regno].freq, regno); 983 update_lives (spill_regno, true); 984 lra_setup_reg_renumber (spill_regno, -1, false); 985 } 986 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap); 987 return best_hard_regno; 988 } 989 990 /* Assign HARD_REGNO to REGNO. */ 991 static void 992 assign_hard_regno (int hard_regno, int regno) 993 { 994 int i; 995 996 lra_assert (hard_regno >= 0); 997 lra_setup_reg_renumber (regno, hard_regno, true); 998 update_lives (regno, false); 999 for (i = 0; 1000 i < hard_regno_nregs[hard_regno][lra_reg_info[regno].biggest_mode]; 1001 i++) 1002 df_set_regs_ever_live (hard_regno + i, true); 1003 } 1004 1005 /* Array used for sorting different pseudos. */ 1006 static int *sorted_pseudos; 1007 1008 /* The constraints pass is allowed to create equivalences between 1009 pseudos that make the current allocation "incorrect" (in the sense 1010 that pseudos are assigned to hard registers from their own conflict 1011 sets). The global variable lra_risky_transformations_p says 1012 whether this might have happened. 1013 1014 Process pseudos assigned to hard registers (less frequently used 1015 first), spill if a conflict is found, and mark the spilled pseudos 1016 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from 1017 pseudos, assigned to hard registers. */ 1018 static void 1019 setup_live_pseudos_and_spill_after_risky_transforms (bitmap 1020 spilled_pseudo_bitmap) 1021 { 1022 int p, i, j, n, regno, hard_regno; 1023 unsigned int k, conflict_regno; 1024 int val; 1025 HARD_REG_SET conflict_set; 1026 enum machine_mode mode; 1027 lra_live_range_t r; 1028 bitmap_iterator bi; 1029 int max_regno = max_reg_num (); 1030 1031 if (! lra_risky_transformations_p) 1032 { 1033 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1034 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0) 1035 update_lives (i, false); 1036 return; 1037 } 1038 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1039 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0) 1040 sorted_pseudos[n++] = i; 1041 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1042 for (i = n - 1; i >= 0; i--) 1043 { 1044 regno = sorted_pseudos[i]; 1045 hard_regno = reg_renumber[regno]; 1046 lra_assert (hard_regno >= 0); 1047 mode = lra_reg_info[regno].biggest_mode; 1048 sparseset_clear (live_range_hard_reg_pseudos); 1049 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 1050 { 1051 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi) 1052 sparseset_set_bit (live_range_hard_reg_pseudos, k); 1053 for (p = r->start + 1; p <= r->finish; p++) 1054 { 1055 lra_live_range_t r2; 1056 1057 for (r2 = start_point_ranges[p]; 1058 r2 != NULL; 1059 r2 = r2->start_next) 1060 if (live_pseudos_reg_renumber[r2->regno] >= 0) 1061 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno); 1062 } 1063 } 1064 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs); 1065 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs); 1066 val = lra_reg_info[regno].val; 1067 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno) 1068 if (val != lra_reg_info[conflict_regno].val 1069 /* If it is multi-register pseudos they should start on 1070 the same hard register. */ 1071 || hard_regno != reg_renumber[conflict_regno]) 1072 add_to_hard_reg_set (&conflict_set, 1073 lra_reg_info[conflict_regno].biggest_mode, 1074 reg_renumber[conflict_regno]); 1075 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno)) 1076 { 1077 update_lives (regno, false); 1078 continue; 1079 } 1080 bitmap_set_bit (spilled_pseudo_bitmap, regno); 1081 for (j = 0; 1082 j < hard_regno_nregs[hard_regno][PSEUDO_REGNO_MODE (regno)]; 1083 j++) 1084 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq; 1085 reg_renumber[regno] = -1; 1086 if (lra_dump_file != NULL) 1087 fprintf (lra_dump_file, " Spill r%d after risky transformations\n", 1088 regno); 1089 } 1090 } 1091 1092 /* Improve allocation by assigning the same hard regno of inheritance 1093 pseudos to the connected pseudos. We need this because inheritance 1094 pseudos are allocated after reload pseudos in the thread and when 1095 we assign a hard register to a reload pseudo we don't know yet that 1096 the connected inheritance pseudos can get the same hard register. 1097 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */ 1098 static void 1099 improve_inheritance (bitmap changed_pseudos) 1100 { 1101 unsigned int k; 1102 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n; 1103 lra_copy_t cp, next_cp; 1104 bitmap_iterator bi; 1105 1106 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES) 1107 return; 1108 n = 0; 1109 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi) 1110 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0) 1111 sorted_pseudos[n++] = k; 1112 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1113 for (i = 0; i < n; i++) 1114 { 1115 regno = sorted_pseudos[i]; 1116 hard_regno = reg_renumber[regno]; 1117 lra_assert (hard_regno >= 0); 1118 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp) 1119 { 1120 if (cp->regno1 == regno) 1121 { 1122 next_cp = cp->regno1_next; 1123 another_regno = cp->regno2; 1124 } 1125 else if (cp->regno2 == regno) 1126 { 1127 next_cp = cp->regno2_next; 1128 another_regno = cp->regno1; 1129 } 1130 else 1131 gcc_unreachable (); 1132 /* Don't change reload pseudo allocation. It might have 1133 this allocation for a purpose and changing it can result 1134 in LRA cycling. */ 1135 if ((another_regno < lra_constraint_new_regno_start 1136 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno)) 1137 && (another_hard_regno = reg_renumber[another_regno]) >= 0 1138 && another_hard_regno != hard_regno) 1139 { 1140 if (lra_dump_file != NULL) 1141 fprintf 1142 (lra_dump_file, 1143 " Improving inheritance for %d(%d) and %d(%d)...\n", 1144 regno, hard_regno, another_regno, another_hard_regno); 1145 update_lives (another_regno, true); 1146 lra_setup_reg_renumber (another_regno, -1, false); 1147 if (hard_regno 1148 == find_hard_regno_for (another_regno, &cost, hard_regno)) 1149 assign_hard_regno (hard_regno, another_regno); 1150 else 1151 assign_hard_regno (another_hard_regno, another_regno); 1152 bitmap_set_bit (changed_pseudos, another_regno); 1153 } 1154 } 1155 } 1156 } 1157 1158 1159 /* Bitmap finally containing all pseudos spilled on this assignment 1160 pass. */ 1161 static bitmap_head all_spilled_pseudos; 1162 /* All pseudos whose allocation was changed. */ 1163 static bitmap_head changed_pseudo_bitmap; 1164 1165 /* Assign hard registers to reload pseudos and other pseudos. */ 1166 static void 1167 assign_by_spills (void) 1168 { 1169 int i, n, nfails, iter, regno, hard_regno, cost, restore_regno; 1170 rtx insn; 1171 basic_block bb; 1172 bitmap_head changed_insns, do_not_assign_nonreload_pseudos; 1173 unsigned int u; 1174 bitmap_iterator bi; 1175 bool reload_p; 1176 int max_regno = max_reg_num (); 1177 1178 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++) 1179 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0 1180 && regno_allocno_class_array[i] != NO_REGS) 1181 sorted_pseudos[n++] = i; 1182 bitmap_initialize (&insn_conflict_pseudos, ®_obstack); 1183 bitmap_initialize (&spill_pseudos_bitmap, ®_obstack); 1184 bitmap_initialize (&best_spill_pseudos_bitmap, ®_obstack); 1185 update_hard_regno_preference_check = XCNEWVEC (int, max_regno); 1186 curr_update_hard_regno_preference_check = 0; 1187 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check)); 1188 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1189 bitmap_initialize (&try_hard_reg_pseudos[i], ®_obstack); 1190 curr_pseudo_check = 0; 1191 bitmap_initialize (&changed_insns, ®_obstack); 1192 bitmap_initialize (&non_reload_pseudos, ®_obstack); 1193 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs); 1194 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos); 1195 for (iter = 0; iter <= 1; iter++) 1196 { 1197 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); 1198 nfails = 0; 1199 for (i = 0; i < n; i++) 1200 { 1201 regno = sorted_pseudos[i]; 1202 if (lra_dump_file != NULL) 1203 fprintf (lra_dump_file, " Assigning to %d " 1204 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n", 1205 regno, reg_class_names[regno_allocno_class_array[regno]], 1206 ORIGINAL_REGNO (regno_reg_rtx[regno]), 1207 lra_reg_info[regno].freq, regno_assign_info[regno].first, 1208 regno_assign_info[regno_assign_info[regno].first].freq); 1209 hard_regno = find_hard_regno_for (regno, &cost, -1); 1210 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno); 1211 if (hard_regno < 0 && reload_p) 1212 hard_regno = spill_for (regno, &all_spilled_pseudos); 1213 if (hard_regno < 0) 1214 { 1215 if (reload_p) 1216 sorted_pseudos[nfails++] = regno; 1217 } 1218 else 1219 { 1220 /* This register might have been spilled by the previous 1221 pass. Indicate that it is no longer spilled. */ 1222 bitmap_clear_bit (&all_spilled_pseudos, regno); 1223 assign_hard_regno (hard_regno, regno); 1224 if (! reload_p) 1225 /* As non-reload pseudo assignment is changed we 1226 should reconsider insns referring for the 1227 pseudo. */ 1228 bitmap_set_bit (&changed_pseudo_bitmap, regno); 1229 } 1230 } 1231 if (nfails == 0) 1232 break; 1233 if (iter > 0) 1234 { 1235 /* We did not assign hard regs to reload pseudos after two 1236 iteration. It means something is wrong with asm insn 1237 constraints. Report it. */ 1238 bool asm_p = false; 1239 bitmap_head failed_reload_insns; 1240 1241 bitmap_initialize (&failed_reload_insns, ®_obstack); 1242 for (i = 0; i < nfails; i++) 1243 { 1244 regno = sorted_pseudos[i]; 1245 bitmap_ior_into (&failed_reload_insns, 1246 &lra_reg_info[regno].insn_bitmap); 1247 /* Assign an arbitrary hard register of regno class to 1248 avoid further trouble with the asm insns. */ 1249 bitmap_clear_bit (&all_spilled_pseudos, regno); 1250 assign_hard_regno 1251 (ira_class_hard_regs[regno_allocno_class_array[regno]][0], 1252 regno); 1253 } 1254 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi) 1255 { 1256 insn = lra_insn_recog_data[u]->insn; 1257 if (asm_noperands (PATTERN (insn)) >= 0) 1258 { 1259 asm_p = true; 1260 error_for_asm (insn, 1261 "%<asm%> operand has impossible constraints"); 1262 /* Avoid further trouble with this insn. 1263 For asm goto, instead of fixing up all the edges 1264 just clear the template and clear input operands 1265 (asm goto doesn't have any output operands). */ 1266 if (JUMP_P (insn)) 1267 { 1268 rtx asm_op = extract_asm_operands (PATTERN (insn)); 1269 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup (""); 1270 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0); 1271 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0); 1272 lra_update_insn_regno_info (insn); 1273 } 1274 else 1275 { 1276 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx); 1277 lra_set_insn_deleted (insn); 1278 } 1279 } 1280 } 1281 gcc_assert (asm_p); 1282 break; 1283 } 1284 /* This is a very rare event. We can not assign a hard 1285 register to reload pseudo because the hard register was 1286 assigned to another reload pseudo on a previous 1287 assignment pass. For x86 example, on the 1st pass we 1288 assigned CX (although another hard register could be used 1289 for this) to reload pseudo in an insn, on the 2nd pass we 1290 need CX (and only this) hard register for a new reload 1291 pseudo in the same insn. */ 1292 if (lra_dump_file != NULL) 1293 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n"); 1294 for (i = 0; i < nfails; i++) 1295 { 1296 if (lra_dump_file != NULL) 1297 fprintf (lra_dump_file, " Reload r%d assignment failure\n", 1298 sorted_pseudos[i]); 1299 bitmap_ior_into (&changed_insns, 1300 &lra_reg_info[sorted_pseudos[i]].insn_bitmap); 1301 } 1302 1303 /* FIXME: Look up the changed insns in the cached LRA insn data using 1304 an EXECUTE_IF_SET_IN_BITMAP over changed_insns. */ 1305 FOR_EACH_BB (bb) 1306 FOR_BB_INSNS (bb, insn) 1307 if (bitmap_bit_p (&changed_insns, INSN_UID (insn))) 1308 { 1309 lra_insn_recog_data_t data; 1310 struct lra_insn_reg *r; 1311 1312 data = lra_get_insn_recog_data (insn); 1313 for (r = data->regs; r != NULL; r = r->next) 1314 { 1315 regno = r->regno; 1316 /* A reload pseudo did not get a hard register on the 1317 first iteration because of the conflict with 1318 another reload pseudos in the same insn. So we 1319 consider only reload pseudos assigned to hard 1320 registers. We shall exclude inheritance pseudos as 1321 they can occur in original insns (not reload ones). 1322 We can omit the check for split pseudos because 1323 they occur only in move insns containing non-reload 1324 pseudos. */ 1325 if (regno < lra_constraint_new_regno_start 1326 || bitmap_bit_p (&lra_inheritance_pseudos, regno) 1327 || reg_renumber[regno] < 0) 1328 continue; 1329 sorted_pseudos[nfails++] = regno; 1330 if (lra_dump_file != NULL) 1331 fprintf (lra_dump_file, 1332 " Spill reload r%d(hr=%d, freq=%d)\n", 1333 regno, reg_renumber[regno], 1334 lra_reg_info[regno].freq); 1335 update_lives (regno, true); 1336 lra_setup_reg_renumber (regno, -1, false); 1337 } 1338 } 1339 n = nfails; 1340 } 1341 improve_inheritance (&changed_pseudo_bitmap); 1342 bitmap_clear (&non_reload_pseudos); 1343 bitmap_clear (&changed_insns); 1344 if (! lra_simple_p) 1345 { 1346 /* We should not assign to original pseudos of inheritance 1347 pseudos or split pseudos if any its inheritance pseudo did 1348 not get hard register or any its split pseudo was not split 1349 because undo inheritance/split pass will extend live range of 1350 such inheritance or split pseudos. */ 1351 bitmap_initialize (&do_not_assign_nonreload_pseudos, ®_obstack); 1352 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi) 1353 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0 1354 && reg_renumber[u] < 0 1355 && bitmap_bit_p (&lra_inheritance_pseudos, u)) 1356 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno); 1357 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi) 1358 if ((restore_regno = lra_reg_info[u].restore_regno) >= 0 1359 && reg_renumber[u] >= 0) 1360 bitmap_set_bit (&do_not_assign_nonreload_pseudos, restore_regno); 1361 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1362 if (((i < lra_constraint_new_regno_start 1363 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i)) 1364 || (bitmap_bit_p (&lra_inheritance_pseudos, i) 1365 && lra_reg_info[i].restore_regno >= 0) 1366 || (bitmap_bit_p (&lra_split_regs, i) 1367 && lra_reg_info[i].restore_regno >= 0) 1368 || bitmap_bit_p (&lra_optional_reload_pseudos, i)) 1369 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0 1370 && regno_allocno_class_array[i] != NO_REGS) 1371 sorted_pseudos[n++] = i; 1372 bitmap_clear (&do_not_assign_nonreload_pseudos); 1373 if (n != 0 && lra_dump_file != NULL) 1374 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n"); 1375 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1376 for (i = 0; i < n; i++) 1377 { 1378 regno = sorted_pseudos[i]; 1379 hard_regno = find_hard_regno_for (regno, &cost, -1); 1380 if (hard_regno >= 0) 1381 { 1382 assign_hard_regno (hard_regno, regno); 1383 /* We change allocation for non-reload pseudo on this 1384 iteration -- mark the pseudo for invalidation of used 1385 alternatives of insns containing the pseudo. */ 1386 bitmap_set_bit (&changed_pseudo_bitmap, regno); 1387 } 1388 } 1389 } 1390 free (update_hard_regno_preference_check); 1391 bitmap_clear (&best_spill_pseudos_bitmap); 1392 bitmap_clear (&spill_pseudos_bitmap); 1393 bitmap_clear (&insn_conflict_pseudos); 1394 } 1395 1396 1397 /* Entry function to assign hard registers to new reload pseudos 1398 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling 1399 of old pseudos) and possibly to the old pseudos. The function adds 1400 what insns to process for the next constraint pass. Those are all 1401 insns who contains non-reload and non-inheritance pseudos with 1402 changed allocation. 1403 1404 Return true if we did not spill any non-reload and non-inheritance 1405 pseudos. */ 1406 bool 1407 lra_assign (void) 1408 { 1409 int i; 1410 unsigned int u; 1411 bitmap_iterator bi; 1412 bitmap_head insns_to_process; 1413 bool no_spills_p; 1414 int max_regno = max_reg_num (); 1415 1416 timevar_push (TV_LRA_ASSIGN); 1417 init_lives (); 1418 sorted_pseudos = XNEWVEC (int, max_regno); 1419 sorted_reload_pseudos = XNEWVEC (int, max_regno); 1420 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno); 1421 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1422 regno_allocno_class_array[i] = lra_get_allocno_class (i); 1423 init_regno_assign_info (); 1424 bitmap_initialize (&all_spilled_pseudos, ®_obstack); 1425 create_live_range_start_chains (); 1426 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos); 1427 #ifdef ENABLE_CHECKING 1428 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1429 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0 1430 && lra_reg_info[i].call_p 1431 && overlaps_hard_reg_set_p (call_used_reg_set, 1432 PSEUDO_REGNO_MODE (i), reg_renumber[i])) 1433 gcc_unreachable (); 1434 #endif 1435 /* Setup insns to process on the next constraint pass. */ 1436 bitmap_initialize (&changed_pseudo_bitmap, ®_obstack); 1437 init_live_reload_and_inheritance_pseudos (); 1438 assign_by_spills (); 1439 finish_live_reload_and_inheritance_pseudos (); 1440 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos); 1441 no_spills_p = true; 1442 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi) 1443 /* We ignore spilled pseudos created on last inheritance pass 1444 because they will be removed. */ 1445 if (lra_reg_info[u].restore_regno < 0) 1446 { 1447 no_spills_p = false; 1448 break; 1449 } 1450 finish_live_range_start_chains (); 1451 bitmap_clear (&all_spilled_pseudos); 1452 bitmap_initialize (&insns_to_process, ®_obstack); 1453 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi) 1454 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap); 1455 bitmap_clear (&changed_pseudo_bitmap); 1456 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi) 1457 { 1458 lra_push_insn_by_uid (u); 1459 /* Invalidate alternatives for insn should be processed. */ 1460 lra_set_used_insn_alternative_by_uid (u, -1); 1461 } 1462 bitmap_clear (&insns_to_process); 1463 finish_regno_assign_info (); 1464 free (regno_allocno_class_array); 1465 free (sorted_pseudos); 1466 free (sorted_reload_pseudos); 1467 finish_lives (); 1468 timevar_pop (TV_LRA_ASSIGN); 1469 return no_spills_p; 1470 } 1471