1 /* Assign reload pseudos. 2 Copyright (C) 2010-2018 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 "backend.h" 81 #include "target.h" 82 #include "rtl.h" 83 #include "tree.h" 84 #include "predict.h" 85 #include "df.h" 86 #include "memmodel.h" 87 #include "tm_p.h" 88 #include "insn-config.h" 89 #include "regs.h" 90 #include "ira.h" 91 #include "recog.h" 92 #include "rtl-error.h" 93 #include "sparseset.h" 94 #include "params.h" 95 #include "lra.h" 96 #include "lra-int.h" 97 98 /* Current iteration number of the pass and current iteration number 99 of the pass after the latest spill pass when any former reload 100 pseudo was spilled. */ 101 int lra_assignment_iter; 102 int lra_assignment_iter_after_spill; 103 104 /* Flag of spilling former reload pseudos on this pass. */ 105 static bool former_reload_pseudo_spill_p; 106 107 /* Array containing corresponding values of function 108 lra_get_allocno_class. It is used to speed up the code. */ 109 static enum reg_class *regno_allocno_class_array; 110 111 /* Array containing lengths of pseudo live ranges. It is used to 112 speed up the code. */ 113 static int *regno_live_length; 114 115 /* Information about the thread to which a pseudo belongs. Threads are 116 a set of connected reload and inheritance pseudos with the same set of 117 available hard registers. Lone registers belong to their own threads. */ 118 struct regno_assign_info 119 { 120 /* First/next pseudo of the same thread. */ 121 int first, next; 122 /* Frequency of the thread (execution frequency of only reload 123 pseudos in the thread when the thread contains a reload pseudo). 124 Defined only for the first thread pseudo. */ 125 int freq; 126 }; 127 128 /* Map regno to the corresponding regno assignment info. */ 129 static struct regno_assign_info *regno_assign_info; 130 131 /* All inherited, subreg or optional pseudos created before last spill 132 sub-pass. Such pseudos are permitted to get memory instead of hard 133 regs. */ 134 static bitmap_head non_reload_pseudos; 135 136 /* Process a pseudo copy with execution frequency COPY_FREQ connecting 137 REGNO1 and REGNO2 to form threads. */ 138 static void 139 process_copy_to_form_thread (int regno1, int regno2, int copy_freq) 140 { 141 int last, regno1_first, regno2_first; 142 143 lra_assert (regno1 >= lra_constraint_new_regno_start 144 && regno2 >= lra_constraint_new_regno_start); 145 regno1_first = regno_assign_info[regno1].first; 146 regno2_first = regno_assign_info[regno2].first; 147 if (regno1_first != regno2_first) 148 { 149 for (last = regno2_first; 150 regno_assign_info[last].next >= 0; 151 last = regno_assign_info[last].next) 152 regno_assign_info[last].first = regno1_first; 153 regno_assign_info[last].first = regno1_first; 154 regno_assign_info[last].next = regno_assign_info[regno1_first].next; 155 regno_assign_info[regno1_first].next = regno2_first; 156 regno_assign_info[regno1_first].freq 157 += regno_assign_info[regno2_first].freq; 158 } 159 regno_assign_info[regno1_first].freq -= 2 * copy_freq; 160 lra_assert (regno_assign_info[regno1_first].freq >= 0); 161 } 162 163 /* Initialize REGNO_ASSIGN_INFO and form threads. */ 164 static void 165 init_regno_assign_info (void) 166 { 167 int i, regno1, regno2, max_regno = max_reg_num (); 168 lra_copy_t cp; 169 170 regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno); 171 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 172 { 173 regno_assign_info[i].first = i; 174 regno_assign_info[i].next = -1; 175 regno_assign_info[i].freq = lra_reg_info[i].freq; 176 } 177 /* Form the threads. */ 178 for (i = 0; (cp = lra_get_copy (i)) != NULL; i++) 179 if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start 180 && (regno2 = cp->regno2) >= lra_constraint_new_regno_start 181 && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0 182 && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0 183 && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]] 184 == ira_class_hard_regs_num[regno_allocno_class_array[regno2]])) 185 process_copy_to_form_thread (regno1, regno2, cp->freq); 186 } 187 188 /* Free REGNO_ASSIGN_INFO. */ 189 static void 190 finish_regno_assign_info (void) 191 { 192 free (regno_assign_info); 193 } 194 195 /* The function is used to sort *reload* and *inheritance* pseudos to 196 try to assign them hard registers. We put pseudos from the same 197 thread always nearby. */ 198 static int 199 reload_pseudo_compare_func (const void *v1p, const void *v2p) 200 { 201 int r1 = *(const int *) v1p, r2 = *(const int *) v2p; 202 enum reg_class cl1 = regno_allocno_class_array[r1]; 203 enum reg_class cl2 = regno_allocno_class_array[r2]; 204 int diff; 205 206 lra_assert (r1 >= lra_constraint_new_regno_start 207 && r2 >= lra_constraint_new_regno_start); 208 209 /* Prefer to assign reload registers with smaller classes first to 210 guarantee assignment to all reload registers. */ 211 if ((diff = (ira_class_hard_regs_num[cl1] 212 - ira_class_hard_regs_num[cl2])) != 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 if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq 221 - regno_assign_info[regno_assign_info[r1].first].freq)) != 0) 222 return diff; 223 /* Put pseudos from the thread nearby. */ 224 if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0) 225 return diff; 226 /* Prefer pseudos with longer live ranges. It sets up better 227 prefered hard registers for the thread pseudos and decreases 228 register-register moves between the thread pseudos. */ 229 if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0) 230 return diff; 231 /* If regs are equally good, sort by their numbers, so that the 232 results of qsort leave nothing to chance. */ 233 return r1 - r2; 234 } 235 236 /* The function is used to sort *non-reload* pseudos to try to assign 237 them hard registers. The order calculation is simpler than in the 238 previous function and based on the pseudo frequency usage. */ 239 static int 240 pseudo_compare_func (const void *v1p, const void *v2p) 241 { 242 int r1 = *(const int *) v1p, r2 = *(const int *) v2p; 243 int diff; 244 245 /* Assign hard reg to static chain pointer first pseudo when 246 non-local goto is used. */ 247 if ((diff = (non_spilled_static_chain_regno_p (r2) 248 - non_spilled_static_chain_regno_p (r1))) != 0) 249 return diff; 250 251 /* Prefer to assign more frequently used registers first. */ 252 if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0) 253 return diff; 254 255 /* If regs are equally good, sort by their numbers, so that the 256 results of qsort leave nothing to chance. */ 257 return r1 - r2; 258 } 259 260 /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the 261 pseudo live ranges with given start point. We insert only live 262 ranges of pseudos interesting for assignment purposes. They are 263 reload pseudos and pseudos assigned to hard registers. */ 264 static lra_live_range_t *start_point_ranges; 265 266 /* Used as a flag that a live range is not inserted in the start point 267 chain. */ 268 static struct lra_live_range not_in_chain_mark; 269 270 /* Create and set up START_POINT_RANGES. */ 271 static void 272 create_live_range_start_chains (void) 273 { 274 int i, max_regno; 275 lra_live_range_t r; 276 277 start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point); 278 max_regno = max_reg_num (); 279 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 280 if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0) 281 { 282 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 283 { 284 r->start_next = start_point_ranges[r->start]; 285 start_point_ranges[r->start] = r; 286 } 287 } 288 else 289 { 290 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 291 r->start_next = ¬_in_chain_mark; 292 } 293 } 294 295 /* Insert live ranges of pseudo REGNO into start chains if they are 296 not there yet. */ 297 static void 298 insert_in_live_range_start_chain (int regno) 299 { 300 lra_live_range_t r = lra_reg_info[regno].live_ranges; 301 302 if (r->start_next != ¬_in_chain_mark) 303 return; 304 for (; r != NULL; r = r->next) 305 { 306 r->start_next = start_point_ranges[r->start]; 307 start_point_ranges[r->start] = r; 308 } 309 } 310 311 /* Free START_POINT_RANGES. */ 312 static void 313 finish_live_range_start_chains (void) 314 { 315 gcc_assert (start_point_ranges != NULL); 316 free (start_point_ranges); 317 start_point_ranges = NULL; 318 } 319 320 /* Map: program point -> bitmap of all pseudos living at the point and 321 assigned to hard registers. */ 322 static bitmap_head *live_hard_reg_pseudos; 323 static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack; 324 325 /* reg_renumber corresponding to pseudos marked in 326 live_hard_reg_pseudos. reg_renumber might be not matched to 327 live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects 328 live_hard_reg_pseudos. */ 329 static int *live_pseudos_reg_renumber; 330 331 /* Sparseset used to calculate living hard reg pseudos for some program 332 point range. */ 333 static sparseset live_range_hard_reg_pseudos; 334 335 /* Sparseset used to calculate living reload/inheritance pseudos for 336 some program point range. */ 337 static sparseset live_range_reload_inheritance_pseudos; 338 339 /* Allocate and initialize the data about living pseudos at program 340 points. */ 341 static void 342 init_lives (void) 343 { 344 int i, max_regno = max_reg_num (); 345 346 live_range_hard_reg_pseudos = sparseset_alloc (max_regno); 347 live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno); 348 live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point); 349 bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack); 350 for (i = 0; i < lra_live_max_point; i++) 351 bitmap_initialize (&live_hard_reg_pseudos[i], 352 &live_hard_reg_pseudos_bitmap_obstack); 353 live_pseudos_reg_renumber = XNEWVEC (int, max_regno); 354 for (i = 0; i < max_regno; i++) 355 live_pseudos_reg_renumber[i] = -1; 356 } 357 358 /* Free the data about living pseudos at program points. */ 359 static void 360 finish_lives (void) 361 { 362 sparseset_free (live_range_hard_reg_pseudos); 363 sparseset_free (live_range_reload_inheritance_pseudos); 364 free (live_hard_reg_pseudos); 365 bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack); 366 free (live_pseudos_reg_renumber); 367 } 368 369 /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER 370 entries for pseudo REGNO. Assume that the register has been 371 spilled if FREE_P, otherwise assume that it has been assigned 372 reg_renumber[REGNO] (if >= 0). We also insert the pseudo live 373 ranges in the start chains when it is assumed to be assigned to a 374 hard register because we use the chains of pseudos assigned to hard 375 registers during allocation. */ 376 static void 377 update_lives (int regno, bool free_p) 378 { 379 int p; 380 lra_live_range_t r; 381 382 if (reg_renumber[regno] < 0) 383 return; 384 live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno]; 385 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 386 { 387 for (p = r->start; p <= r->finish; p++) 388 if (free_p) 389 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno); 390 else 391 { 392 bitmap_set_bit (&live_hard_reg_pseudos[p], regno); 393 insert_in_live_range_start_chain (regno); 394 } 395 } 396 } 397 398 /* Sparseset used to calculate reload pseudos conflicting with a given 399 pseudo when we are trying to find a hard register for the given 400 pseudo. */ 401 static sparseset conflict_reload_and_inheritance_pseudos; 402 403 /* Map: program point -> bitmap of all reload and inheritance pseudos 404 living at the point. */ 405 static bitmap_head *live_reload_and_inheritance_pseudos; 406 static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack; 407 408 /* Allocate and initialize data about living reload pseudos at any 409 given program point. */ 410 static void 411 init_live_reload_and_inheritance_pseudos (void) 412 { 413 int i, p, max_regno = max_reg_num (); 414 lra_live_range_t r; 415 416 conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno); 417 live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point); 418 bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack); 419 for (p = 0; p < lra_live_max_point; p++) 420 bitmap_initialize (&live_reload_and_inheritance_pseudos[p], 421 &live_reload_and_inheritance_pseudos_bitmap_obstack); 422 for (i = lra_constraint_new_regno_start; i < max_regno; i++) 423 { 424 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 425 for (p = r->start; p <= r->finish; p++) 426 bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i); 427 } 428 } 429 430 /* Finalize data about living reload pseudos at any given program 431 point. */ 432 static void 433 finish_live_reload_and_inheritance_pseudos (void) 434 { 435 sparseset_free (conflict_reload_and_inheritance_pseudos); 436 free (live_reload_and_inheritance_pseudos); 437 bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack); 438 } 439 440 /* The value used to check that cost of given hard reg is really 441 defined currently. */ 442 static int curr_hard_regno_costs_check = 0; 443 /* Array used to check that cost of the corresponding hard reg (the 444 array element index) is really defined currently. */ 445 static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER]; 446 /* The current costs of allocation of hard regs. Defined only if the 447 value of the corresponding element of the previous array is equal to 448 CURR_HARD_REGNO_COSTS_CHECK. */ 449 static int hard_regno_costs[FIRST_PSEUDO_REGISTER]; 450 451 /* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is 452 not defined yet. */ 453 static inline void 454 adjust_hard_regno_cost (int hard_regno, int incr) 455 { 456 if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check) 457 hard_regno_costs[hard_regno] = 0; 458 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check; 459 hard_regno_costs[hard_regno] += incr; 460 } 461 462 /* Try to find a free hard register for pseudo REGNO. Return the 463 hard register on success and set *COST to the cost of using 464 that register. (If several registers have equal cost, the one with 465 the highest priority wins.) Return -1 on failure. 466 467 If FIRST_P, return the first available hard reg ignoring other 468 criteria, e.g. allocation cost. This approach results in less hard 469 reg pool fragmentation and permit to allocate hard regs to reload 470 pseudos in complicated situations where pseudo sizes are different. 471 472 If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register, 473 otherwise consider all hard registers in REGNO's class. 474 475 If REGNO_SET is not empty, only hard registers from the set are 476 considered. */ 477 static int 478 find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno, 479 bool first_p, HARD_REG_SET regno_set) 480 { 481 HARD_REG_SET conflict_set; 482 int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX; 483 lra_live_range_t r; 484 int p, i, j, rclass_size, best_hard_regno, priority, hard_regno; 485 int hr, conflict_hr, nregs; 486 machine_mode biggest_mode; 487 unsigned int k, conflict_regno; 488 poly_int64 offset; 489 int val, biggest_nregs, nregs_diff; 490 enum reg_class rclass; 491 bitmap_iterator bi; 492 bool *rclass_intersect_p; 493 HARD_REG_SET impossible_start_hard_regs, available_regs; 494 495 if (hard_reg_set_empty_p (regno_set)) 496 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs); 497 else 498 { 499 COMPL_HARD_REG_SET (conflict_set, regno_set); 500 IOR_HARD_REG_SET (conflict_set, lra_no_alloc_regs); 501 } 502 rclass = regno_allocno_class_array[regno]; 503 rclass_intersect_p = ira_reg_classes_intersect_p[rclass]; 504 curr_hard_regno_costs_check++; 505 sparseset_clear (conflict_reload_and_inheritance_pseudos); 506 sparseset_clear (live_range_hard_reg_pseudos); 507 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs); 508 biggest_mode = lra_reg_info[regno].biggest_mode; 509 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 510 { 511 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi) 512 if (rclass_intersect_p[regno_allocno_class_array[k]]) 513 sparseset_set_bit (live_range_hard_reg_pseudos, k); 514 EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start], 515 0, k, bi) 516 if (lra_reg_info[k].preferred_hard_regno1 >= 0 517 && live_pseudos_reg_renumber[k] < 0 518 && rclass_intersect_p[regno_allocno_class_array[k]]) 519 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k); 520 for (p = r->start + 1; p <= r->finish; p++) 521 { 522 lra_live_range_t r2; 523 524 for (r2 = start_point_ranges[p]; 525 r2 != NULL; 526 r2 = r2->start_next) 527 { 528 if (r2->regno >= lra_constraint_new_regno_start 529 && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0 530 && live_pseudos_reg_renumber[r2->regno] < 0 531 && rclass_intersect_p[regno_allocno_class_array[r2->regno]]) 532 sparseset_set_bit (conflict_reload_and_inheritance_pseudos, 533 r2->regno); 534 if (live_pseudos_reg_renumber[r2->regno] >= 0 535 && rclass_intersect_p[regno_allocno_class_array[r2->regno]]) 536 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno); 537 } 538 } 539 } 540 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0) 541 { 542 adjust_hard_regno_cost 543 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1); 544 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0) 545 adjust_hard_regno_cost 546 (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2); 547 } 548 #ifdef STACK_REGS 549 if (lra_reg_info[regno].no_stack_p) 550 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) 551 SET_HARD_REG_BIT (conflict_set, i); 552 #endif 553 sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno); 554 val = lra_reg_info[regno].val; 555 offset = lra_reg_info[regno].offset; 556 CLEAR_HARD_REG_SET (impossible_start_hard_regs); 557 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno) 558 { 559 conflict_hr = live_pseudos_reg_renumber[conflict_regno]; 560 if (lra_reg_val_equal_p (conflict_regno, val, offset)) 561 { 562 conflict_hr = live_pseudos_reg_renumber[conflict_regno]; 563 nregs = hard_regno_nregs (conflict_hr, 564 lra_reg_info[conflict_regno].biggest_mode); 565 /* Remember about multi-register pseudos. For example, 2 566 hard register pseudos can start on the same hard register 567 but can not start on HR and HR+1/HR-1. */ 568 for (hr = conflict_hr + 1; 569 hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs; 570 hr++) 571 SET_HARD_REG_BIT (impossible_start_hard_regs, hr); 572 for (hr = conflict_hr - 1; 573 hr >= 0 && (int) end_hard_regno (biggest_mode, hr) > conflict_hr; 574 hr--) 575 SET_HARD_REG_BIT (impossible_start_hard_regs, hr); 576 } 577 else 578 { 579 machine_mode biggest_conflict_mode 580 = lra_reg_info[conflict_regno].biggest_mode; 581 int biggest_conflict_nregs 582 = hard_regno_nregs (conflict_hr, biggest_conflict_mode); 583 584 nregs_diff 585 = (biggest_conflict_nregs 586 - hard_regno_nregs (conflict_hr, 587 PSEUDO_REGNO_MODE (conflict_regno))); 588 add_to_hard_reg_set (&conflict_set, 589 biggest_conflict_mode, 590 conflict_hr 591 - (WORDS_BIG_ENDIAN ? nregs_diff : 0)); 592 if (hard_reg_set_subset_p (reg_class_contents[rclass], 593 conflict_set)) 594 return -1; 595 } 596 } 597 EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos, 598 conflict_regno) 599 if (!lra_reg_val_equal_p (conflict_regno, val, offset)) 600 { 601 lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0); 602 if ((hard_regno 603 = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0) 604 { 605 adjust_hard_regno_cost 606 (hard_regno, 607 lra_reg_info[conflict_regno].preferred_hard_regno_profit1); 608 if ((hard_regno 609 = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0) 610 adjust_hard_regno_cost 611 (hard_regno, 612 lra_reg_info[conflict_regno].preferred_hard_regno_profit2); 613 } 614 } 615 /* Make sure that all registers in a multi-word pseudo belong to the 616 required class. */ 617 IOR_COMPL_HARD_REG_SET (conflict_set, reg_class_contents[rclass]); 618 lra_assert (rclass != NO_REGS); 619 rclass_size = ira_class_hard_regs_num[rclass]; 620 best_hard_regno = -1; 621 hard_regno = ira_class_hard_regs[rclass][0]; 622 biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode); 623 nregs_diff = (biggest_nregs 624 - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno))); 625 COPY_HARD_REG_SET (available_regs, reg_class_contents[rclass]); 626 AND_COMPL_HARD_REG_SET (available_regs, lra_no_alloc_regs); 627 for (i = 0; i < rclass_size; i++) 628 { 629 if (try_only_hard_regno >= 0) 630 hard_regno = try_only_hard_regno; 631 else 632 hard_regno = ira_class_hard_regs[rclass][i]; 633 if (! overlaps_hard_reg_set_p (conflict_set, 634 PSEUDO_REGNO_MODE (regno), hard_regno) 635 && targetm.hard_regno_mode_ok (hard_regno, 636 PSEUDO_REGNO_MODE (regno)) 637 /* We can not use prohibited_class_mode_regs for all classes 638 because it is not defined for all classes. */ 639 && (ira_allocno_class_translate[rclass] != rclass 640 || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs 641 [rclass][PSEUDO_REGNO_MODE (regno)], 642 hard_regno)) 643 && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno) 644 && (nregs_diff == 0 645 || (WORDS_BIG_ENDIAN 646 ? (hard_regno - nregs_diff >= 0 647 && TEST_HARD_REG_BIT (available_regs, 648 hard_regno - nregs_diff)) 649 : TEST_HARD_REG_BIT (available_regs, 650 hard_regno + nregs_diff)))) 651 { 652 if (hard_regno_costs_check[hard_regno] 653 != curr_hard_regno_costs_check) 654 { 655 hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check; 656 hard_regno_costs[hard_regno] = 0; 657 } 658 for (j = 0; 659 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)); 660 j++) 661 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j) 662 && ! df_regs_ever_live_p (hard_regno + j)) 663 /* It needs save restore. */ 664 hard_regno_costs[hard_regno] 665 += (2 666 * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) 667 + 1); 668 priority = targetm.register_priority (hard_regno); 669 if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost 670 || (hard_regno_costs[hard_regno] == best_cost 671 && (priority > best_priority 672 || (targetm.register_usage_leveling_p () 673 && priority == best_priority 674 && best_usage > lra_hard_reg_usage[hard_regno])))) 675 { 676 best_hard_regno = hard_regno; 677 best_cost = hard_regno_costs[hard_regno]; 678 best_priority = priority; 679 best_usage = lra_hard_reg_usage[hard_regno]; 680 } 681 } 682 if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0)) 683 break; 684 } 685 if (best_hard_regno >= 0) 686 *cost = best_cost - lra_reg_info[regno].freq; 687 return best_hard_regno; 688 } 689 690 /* A wrapper for find_hard_regno_for_1 (see comments for that function 691 description). This function tries to find a hard register for 692 preferred class first if it is worth. */ 693 static int 694 find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p) 695 { 696 int hard_regno; 697 HARD_REG_SET regno_set; 698 699 /* Only original pseudos can have a different preferred class. */ 700 if (try_only_hard_regno < 0 && regno < lra_new_regno_start) 701 { 702 enum reg_class pref_class = reg_preferred_class (regno); 703 704 if (regno_allocno_class_array[regno] != pref_class) 705 { 706 hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p, 707 reg_class_contents[pref_class]); 708 if (hard_regno >= 0) 709 return hard_regno; 710 } 711 } 712 CLEAR_HARD_REG_SET (regno_set); 713 return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p, 714 regno_set); 715 } 716 717 /* Current value used for checking elements in 718 update_hard_regno_preference_check. */ 719 static int curr_update_hard_regno_preference_check; 720 /* If an element value is equal to the above variable value, then the 721 corresponding regno has been processed for preference 722 propagation. */ 723 static int *update_hard_regno_preference_check; 724 725 /* Update the preference for using HARD_REGNO for pseudos that are 726 connected directly or indirectly with REGNO. Apply divisor DIV 727 to any preference adjustments. 728 729 The more indirectly a pseudo is connected, the smaller its effect 730 should be. We therefore increase DIV on each "hop". */ 731 static void 732 update_hard_regno_preference (int regno, int hard_regno, int div) 733 { 734 int another_regno, cost; 735 lra_copy_t cp, next_cp; 736 737 /* Search depth 5 seems to be enough. */ 738 if (div > (1 << 5)) 739 return; 740 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp) 741 { 742 if (cp->regno1 == regno) 743 { 744 next_cp = cp->regno1_next; 745 another_regno = cp->regno2; 746 } 747 else if (cp->regno2 == regno) 748 { 749 next_cp = cp->regno2_next; 750 another_regno = cp->regno1; 751 } 752 else 753 gcc_unreachable (); 754 if (reg_renumber[another_regno] < 0 755 && (update_hard_regno_preference_check[another_regno] 756 != curr_update_hard_regno_preference_check)) 757 { 758 update_hard_regno_preference_check[another_regno] 759 = curr_update_hard_regno_preference_check; 760 cost = cp->freq < div ? 1 : cp->freq / div; 761 lra_setup_reload_pseudo_preferenced_hard_reg 762 (another_regno, hard_regno, cost); 763 update_hard_regno_preference (another_regno, hard_regno, div * 2); 764 } 765 } 766 } 767 768 /* Return prefix title for pseudo REGNO. */ 769 static const char * 770 pseudo_prefix_title (int regno) 771 { 772 return 773 (regno < lra_constraint_new_regno_start ? "" 774 : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance " 775 : bitmap_bit_p (&lra_split_regs, regno) ? "split " 776 : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload " 777 : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload " 778 : "reload "); 779 } 780 781 /* Update REG_RENUMBER and other pseudo preferences by assignment of 782 HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */ 783 void 784 lra_setup_reg_renumber (int regno, int hard_regno, bool print_p) 785 { 786 int i, hr; 787 788 /* We can not just reassign hard register. */ 789 lra_assert (hard_regno < 0 || reg_renumber[regno] < 0); 790 if ((hr = hard_regno) < 0) 791 hr = reg_renumber[regno]; 792 reg_renumber[regno] = hard_regno; 793 lra_assert (hr >= 0); 794 for (i = 0; i < hard_regno_nregs (hr, PSEUDO_REGNO_MODE (regno)); i++) 795 if (hard_regno < 0) 796 lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq; 797 else 798 lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq; 799 if (print_p && lra_dump_file != NULL) 800 fprintf (lra_dump_file, " Assign %d to %sr%d (freq=%d)\n", 801 reg_renumber[regno], pseudo_prefix_title (regno), 802 regno, lra_reg_info[regno].freq); 803 if (hard_regno >= 0) 804 { 805 curr_update_hard_regno_preference_check++; 806 update_hard_regno_preference (regno, hard_regno, 1); 807 } 808 } 809 810 /* Pseudos which occur in insns containing a particular pseudo. */ 811 static bitmap_head insn_conflict_pseudos; 812 813 /* Bitmaps used to contain spill pseudos for given pseudo hard regno 814 and best spill pseudos for given pseudo (and best hard regno). */ 815 static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap; 816 817 /* Current pseudo check for validity of elements in 818 TRY_HARD_REG_PSEUDOS. */ 819 static int curr_pseudo_check; 820 /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */ 821 static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER]; 822 /* Pseudos who hold given hard register at the considered points. */ 823 static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER]; 824 825 /* Set up try_hard_reg_pseudos for given program point P and class 826 RCLASS. Those are pseudos living at P and assigned to a hard 827 register of RCLASS. In other words, those are pseudos which can be 828 spilled to assign a hard register of RCLASS to a pseudo living at 829 P. */ 830 static void 831 setup_try_hard_regno_pseudos (int p, enum reg_class rclass) 832 { 833 int i, hard_regno; 834 machine_mode mode; 835 unsigned int spill_regno; 836 bitmap_iterator bi; 837 838 /* Find what pseudos could be spilled. */ 839 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi) 840 { 841 mode = PSEUDO_REGNO_MODE (spill_regno); 842 hard_regno = live_pseudos_reg_renumber[spill_regno]; 843 if (overlaps_hard_reg_set_p (reg_class_contents[rclass], 844 mode, hard_regno)) 845 { 846 for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--) 847 { 848 if (try_hard_reg_pseudos_check[hard_regno + i] 849 != curr_pseudo_check) 850 { 851 try_hard_reg_pseudos_check[hard_regno + i] 852 = curr_pseudo_check; 853 bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]); 854 } 855 bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i], 856 spill_regno); 857 } 858 } 859 } 860 } 861 862 /* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary 863 assignment means that we might undo the data change. */ 864 static void 865 assign_temporarily (int regno, int hard_regno) 866 { 867 int p; 868 lra_live_range_t r; 869 870 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 871 { 872 for (p = r->start; p <= r->finish; p++) 873 if (hard_regno < 0) 874 bitmap_clear_bit (&live_hard_reg_pseudos[p], regno); 875 else 876 { 877 bitmap_set_bit (&live_hard_reg_pseudos[p], regno); 878 insert_in_live_range_start_chain (regno); 879 } 880 } 881 live_pseudos_reg_renumber[regno] = hard_regno; 882 } 883 884 /* Return true iff there is a reason why pseudo SPILL_REGNO should not 885 be spilled. */ 886 static bool 887 must_not_spill_p (unsigned spill_regno) 888 { 889 if ((pic_offset_table_rtx != NULL 890 && spill_regno == REGNO (pic_offset_table_rtx)) 891 || ((int) spill_regno >= lra_constraint_new_regno_start 892 && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno) 893 && ! bitmap_bit_p (&lra_split_regs, spill_regno) 894 && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno) 895 && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno))) 896 return true; 897 /* A reload pseudo that requires a singleton register class should 898 not be spilled. 899 FIXME: this mitigates the issue on certain i386 patterns, but 900 does not solve the general case where existing reloads fully 901 cover a limited register class. */ 902 if (!bitmap_bit_p (&non_reload_pseudos, spill_regno) 903 && reg_class_size [reg_preferred_class (spill_regno)] == 1 904 && reg_alternate_class (spill_regno) == NO_REGS) 905 return true; 906 return false; 907 } 908 909 /* Array used for sorting reload pseudos for subsequent allocation 910 after spilling some pseudo. */ 911 static int *sorted_reload_pseudos; 912 913 /* Spill some pseudos for a reload pseudo REGNO and return hard 914 register which should be used for pseudo after spilling. The 915 function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we 916 choose hard register (and pseudos occupying the hard registers and 917 to be spilled), we take into account not only how REGNO will 918 benefit from the spills but also how other reload pseudos not yet 919 assigned to hard registers benefit from the spills too. In very 920 rare cases, the function can fail and return -1. 921 922 If FIRST_P, return the first available hard reg ignoring other 923 criteria, e.g. allocation cost and cost of spilling non-reload 924 pseudos. This approach results in less hard reg pool fragmentation 925 and permit to allocate hard regs to reload pseudos in complicated 926 situations where pseudo sizes are different. */ 927 static int 928 spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p) 929 { 930 int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size; 931 int reload_hard_regno, reload_cost; 932 bool static_p, best_static_p; 933 machine_mode mode; 934 enum reg_class rclass; 935 unsigned int spill_regno, reload_regno, uid; 936 int insn_pseudos_num, best_insn_pseudos_num; 937 int bad_spills_num, smallest_bad_spills_num; 938 lra_live_range_t r; 939 bitmap_iterator bi; 940 941 rclass = regno_allocno_class_array[regno]; 942 lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS); 943 bitmap_clear (&insn_conflict_pseudos); 944 bitmap_clear (&best_spill_pseudos_bitmap); 945 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi) 946 { 947 struct lra_insn_reg *ir; 948 949 for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next) 950 if (ir->regno >= FIRST_PSEUDO_REGISTER) 951 bitmap_set_bit (&insn_conflict_pseudos, ir->regno); 952 } 953 best_hard_regno = -1; 954 best_cost = INT_MAX; 955 best_static_p = TRUE; 956 best_insn_pseudos_num = INT_MAX; 957 smallest_bad_spills_num = INT_MAX; 958 rclass_size = ira_class_hard_regs_num[rclass]; 959 mode = PSEUDO_REGNO_MODE (regno); 960 /* Invalidate try_hard_reg_pseudos elements. */ 961 curr_pseudo_check++; 962 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 963 for (p = r->start; p <= r->finish; p++) 964 setup_try_hard_regno_pseudos (p, rclass); 965 for (i = 0; i < rclass_size; i++) 966 { 967 hard_regno = ira_class_hard_regs[rclass][i]; 968 bitmap_clear (&spill_pseudos_bitmap); 969 for (j = hard_regno_nregs (hard_regno, mode) - 1; j >= 0; j--) 970 { 971 if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check) 972 continue; 973 lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j])); 974 bitmap_ior_into (&spill_pseudos_bitmap, 975 &try_hard_reg_pseudos[hard_regno + j]); 976 } 977 /* Spill pseudos. */ 978 static_p = false; 979 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 980 if (must_not_spill_p (spill_regno)) 981 goto fail; 982 else if (non_spilled_static_chain_regno_p (spill_regno)) 983 static_p = true; 984 insn_pseudos_num = 0; 985 bad_spills_num = 0; 986 if (lra_dump_file != NULL) 987 fprintf (lra_dump_file, " Trying %d:", hard_regno); 988 sparseset_clear (live_range_reload_inheritance_pseudos); 989 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 990 { 991 if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno)) 992 insn_pseudos_num++; 993 if (spill_regno >= (unsigned int) lra_bad_spill_regno_start) 994 bad_spills_num++; 995 for (r = lra_reg_info[spill_regno].live_ranges; 996 r != NULL; 997 r = r->next) 998 { 999 for (p = r->start; p <= r->finish; p++) 1000 { 1001 lra_live_range_t r2; 1002 1003 for (r2 = start_point_ranges[p]; 1004 r2 != NULL; 1005 r2 = r2->start_next) 1006 if (r2->regno >= lra_constraint_new_regno_start) 1007 sparseset_set_bit (live_range_reload_inheritance_pseudos, 1008 r2->regno); 1009 } 1010 } 1011 } 1012 n = 0; 1013 if (sparseset_cardinality (live_range_reload_inheritance_pseudos) 1014 <= (unsigned)LRA_MAX_CONSIDERED_RELOAD_PSEUDOS) 1015 EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos, 1016 reload_regno) 1017 if ((int) reload_regno != regno 1018 && (ira_reg_classes_intersect_p 1019 [rclass][regno_allocno_class_array[reload_regno]]) 1020 && live_pseudos_reg_renumber[reload_regno] < 0 1021 && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0) 1022 sorted_reload_pseudos[n++] = reload_regno; 1023 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 1024 { 1025 update_lives (spill_regno, true); 1026 if (lra_dump_file != NULL) 1027 fprintf (lra_dump_file, " spill %d(freq=%d)", 1028 spill_regno, lra_reg_info[spill_regno].freq); 1029 } 1030 hard_regno = find_hard_regno_for (regno, &cost, -1, first_p); 1031 if (hard_regno >= 0) 1032 { 1033 assign_temporarily (regno, hard_regno); 1034 qsort (sorted_reload_pseudos, n, sizeof (int), 1035 reload_pseudo_compare_func); 1036 for (j = 0; j < n; j++) 1037 { 1038 reload_regno = sorted_reload_pseudos[j]; 1039 lra_assert (live_pseudos_reg_renumber[reload_regno] < 0); 1040 if ((reload_hard_regno 1041 = find_hard_regno_for (reload_regno, 1042 &reload_cost, -1, first_p)) >= 0) 1043 { 1044 if (lra_dump_file != NULL) 1045 fprintf (lra_dump_file, " assign %d(cost=%d)", 1046 reload_regno, reload_cost); 1047 assign_temporarily (reload_regno, reload_hard_regno); 1048 cost += reload_cost; 1049 } 1050 } 1051 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 1052 { 1053 rtx_insn_list *x; 1054 1055 cost += lra_reg_info[spill_regno].freq; 1056 if (ira_reg_equiv[spill_regno].memory != NULL 1057 || ira_reg_equiv[spill_regno].constant != NULL) 1058 for (x = ira_reg_equiv[spill_regno].init_insns; 1059 x != NULL; 1060 x = x->next ()) 1061 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ())); 1062 } 1063 /* Avoid spilling static chain pointer pseudo when non-local 1064 goto is used. */ 1065 if ((! static_p && best_static_p) 1066 || (static_p == best_static_p 1067 && (best_insn_pseudos_num > insn_pseudos_num 1068 || (best_insn_pseudos_num == insn_pseudos_num 1069 && (bad_spills_num < smallest_bad_spills_num 1070 || (bad_spills_num == smallest_bad_spills_num 1071 && best_cost > cost)))))) 1072 { 1073 best_insn_pseudos_num = insn_pseudos_num; 1074 smallest_bad_spills_num = bad_spills_num; 1075 best_static_p = static_p; 1076 best_cost = cost; 1077 best_hard_regno = hard_regno; 1078 bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap); 1079 if (lra_dump_file != NULL) 1080 fprintf (lra_dump_file, 1081 " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n", 1082 hard_regno, cost, bad_spills_num, insn_pseudos_num); 1083 } 1084 assign_temporarily (regno, -1); 1085 for (j = 0; j < n; j++) 1086 { 1087 reload_regno = sorted_reload_pseudos[j]; 1088 if (live_pseudos_reg_renumber[reload_regno] >= 0) 1089 assign_temporarily (reload_regno, -1); 1090 } 1091 } 1092 if (lra_dump_file != NULL) 1093 fprintf (lra_dump_file, "\n"); 1094 /* Restore the live hard reg pseudo info for spilled pseudos. */ 1095 EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi) 1096 update_lives (spill_regno, false); 1097 fail: 1098 ; 1099 } 1100 /* Spill: */ 1101 EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi) 1102 { 1103 if ((int) spill_regno >= lra_constraint_new_regno_start) 1104 former_reload_pseudo_spill_p = true; 1105 if (lra_dump_file != NULL) 1106 fprintf (lra_dump_file, " Spill %sr%d(hr=%d, freq=%d) for r%d\n", 1107 pseudo_prefix_title (spill_regno), 1108 spill_regno, reg_renumber[spill_regno], 1109 lra_reg_info[spill_regno].freq, regno); 1110 update_lives (spill_regno, true); 1111 lra_setup_reg_renumber (spill_regno, -1, false); 1112 } 1113 bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap); 1114 return best_hard_regno; 1115 } 1116 1117 /* Assign HARD_REGNO to REGNO. */ 1118 static void 1119 assign_hard_regno (int hard_regno, int regno) 1120 { 1121 int i; 1122 1123 lra_assert (hard_regno >= 0); 1124 lra_setup_reg_renumber (regno, hard_regno, true); 1125 update_lives (regno, false); 1126 for (i = 0; 1127 i < hard_regno_nregs (hard_regno, lra_reg_info[regno].biggest_mode); 1128 i++) 1129 df_set_regs_ever_live (hard_regno + i, true); 1130 } 1131 1132 /* Array used for sorting different pseudos. */ 1133 static int *sorted_pseudos; 1134 1135 /* The constraints pass is allowed to create equivalences between 1136 pseudos that make the current allocation "incorrect" (in the sense 1137 that pseudos are assigned to hard registers from their own conflict 1138 sets). The global variable lra_risky_transformations_p says 1139 whether this might have happened. 1140 1141 Process pseudos assigned to hard registers (less frequently used 1142 first), spill if a conflict is found, and mark the spilled pseudos 1143 in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from 1144 pseudos, assigned to hard registers. */ 1145 static void 1146 setup_live_pseudos_and_spill_after_risky_transforms (bitmap 1147 spilled_pseudo_bitmap) 1148 { 1149 int p, i, j, n, regno, hard_regno; 1150 unsigned int k, conflict_regno; 1151 poly_int64 offset; 1152 int val; 1153 HARD_REG_SET conflict_set; 1154 machine_mode mode; 1155 lra_live_range_t r; 1156 bitmap_iterator bi; 1157 int max_regno = max_reg_num (); 1158 1159 if (! lra_risky_transformations_p) 1160 { 1161 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1162 if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0) 1163 update_lives (i, false); 1164 return; 1165 } 1166 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1167 if ((pic_offset_table_rtx == NULL_RTX 1168 || i != (int) REGNO (pic_offset_table_rtx)) 1169 && reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0) 1170 sorted_pseudos[n++] = i; 1171 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1172 if (pic_offset_table_rtx != NULL_RTX 1173 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER 1174 && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0) 1175 sorted_pseudos[n++] = regno; 1176 for (i = n - 1; i >= 0; i--) 1177 { 1178 regno = sorted_pseudos[i]; 1179 hard_regno = reg_renumber[regno]; 1180 lra_assert (hard_regno >= 0); 1181 mode = lra_reg_info[regno].biggest_mode; 1182 sparseset_clear (live_range_hard_reg_pseudos); 1183 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 1184 { 1185 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi) 1186 sparseset_set_bit (live_range_hard_reg_pseudos, k); 1187 for (p = r->start + 1; p <= r->finish; p++) 1188 { 1189 lra_live_range_t r2; 1190 1191 for (r2 = start_point_ranges[p]; 1192 r2 != NULL; 1193 r2 = r2->start_next) 1194 if (live_pseudos_reg_renumber[r2->regno] >= 0) 1195 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno); 1196 } 1197 } 1198 COPY_HARD_REG_SET (conflict_set, lra_no_alloc_regs); 1199 IOR_HARD_REG_SET (conflict_set, lra_reg_info[regno].conflict_hard_regs); 1200 val = lra_reg_info[regno].val; 1201 offset = lra_reg_info[regno].offset; 1202 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno) 1203 if (!lra_reg_val_equal_p (conflict_regno, val, offset) 1204 /* If it is multi-register pseudos they should start on 1205 the same hard register. */ 1206 || hard_regno != reg_renumber[conflict_regno]) 1207 { 1208 int conflict_hard_regno = reg_renumber[conflict_regno]; 1209 machine_mode biggest_mode = lra_reg_info[conflict_regno].biggest_mode; 1210 int biggest_nregs = hard_regno_nregs (conflict_hard_regno, 1211 biggest_mode); 1212 int nregs_diff 1213 = (biggest_nregs 1214 - hard_regno_nregs (conflict_hard_regno, 1215 PSEUDO_REGNO_MODE (conflict_regno))); 1216 add_to_hard_reg_set (&conflict_set, 1217 biggest_mode, 1218 conflict_hard_regno 1219 - (WORDS_BIG_ENDIAN ? nregs_diff : 0)); 1220 } 1221 if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno)) 1222 { 1223 update_lives (regno, false); 1224 continue; 1225 } 1226 bitmap_set_bit (spilled_pseudo_bitmap, regno); 1227 for (j = 0; 1228 j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)); 1229 j++) 1230 lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq; 1231 reg_renumber[regno] = -1; 1232 if (regno >= lra_constraint_new_regno_start) 1233 former_reload_pseudo_spill_p = true; 1234 if (lra_dump_file != NULL) 1235 fprintf (lra_dump_file, " Spill r%d after risky transformations\n", 1236 regno); 1237 } 1238 } 1239 1240 /* Improve allocation by assigning the same hard regno of inheritance 1241 pseudos to the connected pseudos. We need this because inheritance 1242 pseudos are allocated after reload pseudos in the thread and when 1243 we assign a hard register to a reload pseudo we don't know yet that 1244 the connected inheritance pseudos can get the same hard register. 1245 Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */ 1246 static void 1247 improve_inheritance (bitmap changed_pseudos) 1248 { 1249 unsigned int k; 1250 int regno, another_regno, hard_regno, another_hard_regno, cost, i, n; 1251 lra_copy_t cp, next_cp; 1252 bitmap_iterator bi; 1253 1254 if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES) 1255 return; 1256 n = 0; 1257 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi) 1258 if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0) 1259 sorted_pseudos[n++] = k; 1260 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1261 for (i = 0; i < n; i++) 1262 { 1263 regno = sorted_pseudos[i]; 1264 hard_regno = reg_renumber[regno]; 1265 lra_assert (hard_regno >= 0); 1266 for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp) 1267 { 1268 if (cp->regno1 == regno) 1269 { 1270 next_cp = cp->regno1_next; 1271 another_regno = cp->regno2; 1272 } 1273 else if (cp->regno2 == regno) 1274 { 1275 next_cp = cp->regno2_next; 1276 another_regno = cp->regno1; 1277 } 1278 else 1279 gcc_unreachable (); 1280 /* Don't change reload pseudo allocation. It might have 1281 this allocation for a purpose and changing it can result 1282 in LRA cycling. */ 1283 if ((another_regno < lra_constraint_new_regno_start 1284 || bitmap_bit_p (&lra_inheritance_pseudos, another_regno)) 1285 && (another_hard_regno = reg_renumber[another_regno]) >= 0 1286 && another_hard_regno != hard_regno) 1287 { 1288 if (lra_dump_file != NULL) 1289 fprintf 1290 (lra_dump_file, 1291 " Improving inheritance for %d(%d) and %d(%d)...\n", 1292 regno, hard_regno, another_regno, another_hard_regno); 1293 update_lives (another_regno, true); 1294 lra_setup_reg_renumber (another_regno, -1, false); 1295 if (hard_regno == find_hard_regno_for (another_regno, &cost, 1296 hard_regno, false)) 1297 assign_hard_regno (hard_regno, another_regno); 1298 else 1299 assign_hard_regno (another_hard_regno, another_regno); 1300 bitmap_set_bit (changed_pseudos, another_regno); 1301 } 1302 } 1303 } 1304 } 1305 1306 1307 /* Bitmap finally containing all pseudos spilled on this assignment 1308 pass. */ 1309 static bitmap_head all_spilled_pseudos; 1310 /* All pseudos whose allocation was changed. */ 1311 static bitmap_head changed_pseudo_bitmap; 1312 1313 1314 /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with 1315 REGNO and whose hard regs can be assigned to REGNO. */ 1316 static void 1317 find_all_spills_for (int regno) 1318 { 1319 int p; 1320 lra_live_range_t r; 1321 unsigned int k; 1322 bitmap_iterator bi; 1323 enum reg_class rclass; 1324 bool *rclass_intersect_p; 1325 1326 rclass = regno_allocno_class_array[regno]; 1327 rclass_intersect_p = ira_reg_classes_intersect_p[rclass]; 1328 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 1329 { 1330 EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi) 1331 if (rclass_intersect_p[regno_allocno_class_array[k]]) 1332 sparseset_set_bit (live_range_hard_reg_pseudos, k); 1333 for (p = r->start + 1; p <= r->finish; p++) 1334 { 1335 lra_live_range_t r2; 1336 1337 for (r2 = start_point_ranges[p]; 1338 r2 != NULL; 1339 r2 = r2->start_next) 1340 { 1341 if (live_pseudos_reg_renumber[r2->regno] >= 0 1342 && ! sparseset_bit_p (live_range_hard_reg_pseudos, r2->regno) 1343 && rclass_intersect_p[regno_allocno_class_array[r2->regno]] 1344 && ((int) r2->regno < lra_constraint_new_regno_start 1345 || bitmap_bit_p (&lra_inheritance_pseudos, r2->regno) 1346 || bitmap_bit_p (&lra_split_regs, r2->regno) 1347 || bitmap_bit_p (&lra_optional_reload_pseudos, r2->regno) 1348 /* There is no sense to consider another reload 1349 pseudo if it has the same class. */ 1350 || regno_allocno_class_array[r2->regno] != rclass)) 1351 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno); 1352 } 1353 } 1354 } 1355 } 1356 1357 /* Assign hard registers to reload pseudos and other pseudos. Return 1358 true if we was not able to assign hard registers to all reload 1359 pseudos. */ 1360 static bool 1361 assign_by_spills (void) 1362 { 1363 int i, n, nfails, iter, regno, regno2, hard_regno, cost; 1364 rtx restore_rtx; 1365 bitmap_head changed_insns, do_not_assign_nonreload_pseudos; 1366 unsigned int u, conflict_regno; 1367 bitmap_iterator bi; 1368 bool reload_p, fails_p = false; 1369 int max_regno = max_reg_num (); 1370 1371 for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++) 1372 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0 1373 && regno_allocno_class_array[i] != NO_REGS) 1374 sorted_pseudos[n++] = i; 1375 bitmap_initialize (&insn_conflict_pseudos, ®_obstack); 1376 bitmap_initialize (&spill_pseudos_bitmap, ®_obstack); 1377 bitmap_initialize (&best_spill_pseudos_bitmap, ®_obstack); 1378 update_hard_regno_preference_check = XCNEWVEC (int, max_regno); 1379 curr_update_hard_regno_preference_check = 0; 1380 memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check)); 1381 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1382 bitmap_initialize (&try_hard_reg_pseudos[i], ®_obstack); 1383 curr_pseudo_check = 0; 1384 bitmap_initialize (&changed_insns, ®_obstack); 1385 bitmap_initialize (&non_reload_pseudos, ®_obstack); 1386 bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs); 1387 bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos); 1388 bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos); 1389 for (iter = 0; iter <= 1; iter++) 1390 { 1391 qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); 1392 nfails = 0; 1393 for (i = 0; i < n; i++) 1394 { 1395 regno = sorted_pseudos[i]; 1396 if (reg_renumber[regno] >= 0) 1397 continue; 1398 if (lra_dump_file != NULL) 1399 fprintf (lra_dump_file, " Assigning to %d " 1400 "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n", 1401 regno, reg_class_names[regno_allocno_class_array[regno]], 1402 ORIGINAL_REGNO (regno_reg_rtx[regno]), 1403 lra_reg_info[regno].freq, regno_assign_info[regno].first, 1404 regno_assign_info[regno_assign_info[regno].first].freq); 1405 hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1); 1406 reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno); 1407 if (hard_regno < 0 && reload_p) 1408 hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1); 1409 if (hard_regno < 0) 1410 { 1411 if (reload_p) { 1412 /* Put unassigned reload pseudo first in the 1413 array. */ 1414 regno2 = sorted_pseudos[nfails]; 1415 sorted_pseudos[nfails++] = regno; 1416 sorted_pseudos[i] = regno2; 1417 } 1418 } 1419 else 1420 { 1421 /* This register might have been spilled by the previous 1422 pass. Indicate that it is no longer spilled. */ 1423 bitmap_clear_bit (&all_spilled_pseudos, regno); 1424 assign_hard_regno (hard_regno, regno); 1425 if (! reload_p) 1426 /* As non-reload pseudo assignment is changed we 1427 should reconsider insns referring for the 1428 pseudo. */ 1429 bitmap_set_bit (&changed_pseudo_bitmap, regno); 1430 } 1431 } 1432 if (nfails == 0 || iter > 0) 1433 { 1434 fails_p = nfails != 0; 1435 break; 1436 } 1437 /* This is a very rare event. We can not assign a hard register 1438 to reload pseudo because the hard register was assigned to 1439 another reload pseudo on a previous assignment pass. For x86 1440 example, on the 1st pass we assigned CX (although another 1441 hard register could be used for this) to reload pseudo in an 1442 insn, on the 2nd pass we need CX (and only this) hard 1443 register for a new reload pseudo in the same insn. Another 1444 possible situation may occur in assigning to multi-regs 1445 reload pseudos when hard regs pool is too fragmented even 1446 after spilling non-reload pseudos. 1447 1448 We should do something radical here to succeed. Here we 1449 spill *all* conflicting pseudos and reassign them. */ 1450 if (lra_dump_file != NULL) 1451 fprintf (lra_dump_file, " 2nd iter for reload pseudo assignments:\n"); 1452 sparseset_clear (live_range_hard_reg_pseudos); 1453 for (i = 0; i < nfails; i++) 1454 { 1455 if (lra_dump_file != NULL) 1456 fprintf (lra_dump_file, " Reload r%d assignment failure\n", 1457 sorted_pseudos[i]); 1458 find_all_spills_for (sorted_pseudos[i]); 1459 } 1460 EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno) 1461 { 1462 if ((int) conflict_regno >= lra_constraint_new_regno_start) 1463 { 1464 sorted_pseudos[nfails++] = conflict_regno; 1465 former_reload_pseudo_spill_p = true; 1466 } 1467 else 1468 /* It is better to do reloads before spilling as after the 1469 spill-subpass we will reload memory instead of pseudos 1470 and this will make reusing reload pseudos more 1471 complicated. Going directly to the spill pass in such 1472 case might result in worse code performance or even LRA 1473 cycling if we have few registers. */ 1474 bitmap_set_bit (&all_spilled_pseudos, conflict_regno); 1475 if (lra_dump_file != NULL) 1476 fprintf (lra_dump_file, " Spill %s r%d(hr=%d, freq=%d)\n", 1477 pseudo_prefix_title (conflict_regno), conflict_regno, 1478 reg_renumber[conflict_regno], 1479 lra_reg_info[conflict_regno].freq); 1480 update_lives (conflict_regno, true); 1481 lra_setup_reg_renumber (conflict_regno, -1, false); 1482 } 1483 if (n < nfails) 1484 n = nfails; 1485 } 1486 improve_inheritance (&changed_pseudo_bitmap); 1487 bitmap_clear (&non_reload_pseudos); 1488 bitmap_clear (&changed_insns); 1489 if (! lra_simple_p) 1490 { 1491 /* We should not assign to original pseudos of inheritance 1492 pseudos or split pseudos if any its inheritance pseudo did 1493 not get hard register or any its split pseudo was not split 1494 because undo inheritance/split pass will extend live range of 1495 such inheritance or split pseudos. */ 1496 bitmap_initialize (&do_not_assign_nonreload_pseudos, ®_obstack); 1497 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi) 1498 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX 1499 && REG_P (restore_rtx) 1500 && reg_renumber[u] < 0 1501 && bitmap_bit_p (&lra_inheritance_pseudos, u)) 1502 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx)); 1503 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi) 1504 if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX 1505 && reg_renumber[u] >= 0) 1506 { 1507 lra_assert (REG_P (restore_rtx)); 1508 bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx)); 1509 } 1510 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1511 if (((i < lra_constraint_new_regno_start 1512 && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i)) 1513 || (bitmap_bit_p (&lra_inheritance_pseudos, i) 1514 && lra_reg_info[i].restore_rtx != NULL_RTX) 1515 || (bitmap_bit_p (&lra_split_regs, i) 1516 && lra_reg_info[i].restore_rtx != NULL_RTX) 1517 || bitmap_bit_p (&lra_subreg_reload_pseudos, i) 1518 || bitmap_bit_p (&lra_optional_reload_pseudos, i)) 1519 && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0 1520 && regno_allocno_class_array[i] != NO_REGS) 1521 sorted_pseudos[n++] = i; 1522 bitmap_clear (&do_not_assign_nonreload_pseudos); 1523 if (n != 0 && lra_dump_file != NULL) 1524 fprintf (lra_dump_file, " Reassigning non-reload pseudos\n"); 1525 qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func); 1526 for (i = 0; i < n; i++) 1527 { 1528 regno = sorted_pseudos[i]; 1529 hard_regno = find_hard_regno_for (regno, &cost, -1, false); 1530 if (hard_regno >= 0) 1531 { 1532 assign_hard_regno (hard_regno, regno); 1533 /* We change allocation for non-reload pseudo on this 1534 iteration -- mark the pseudo for invalidation of used 1535 alternatives of insns containing the pseudo. */ 1536 bitmap_set_bit (&changed_pseudo_bitmap, regno); 1537 } 1538 else 1539 { 1540 enum reg_class rclass = lra_get_allocno_class (regno); 1541 enum reg_class spill_class; 1542 1543 if (targetm.spill_class == NULL 1544 || lra_reg_info[regno].restore_rtx == NULL_RTX 1545 || ! bitmap_bit_p (&lra_inheritance_pseudos, regno) 1546 || (spill_class 1547 = ((enum reg_class) 1548 targetm.spill_class 1549 ((reg_class_t) rclass, 1550 PSEUDO_REGNO_MODE (regno)))) == NO_REGS) 1551 continue; 1552 regno_allocno_class_array[regno] = spill_class; 1553 hard_regno = find_hard_regno_for (regno, &cost, -1, false); 1554 if (hard_regno < 0) 1555 regno_allocno_class_array[regno] = rclass; 1556 else 1557 { 1558 setup_reg_classes 1559 (regno, spill_class, spill_class, spill_class); 1560 assign_hard_regno (hard_regno, regno); 1561 bitmap_set_bit (&changed_pseudo_bitmap, regno); 1562 } 1563 } 1564 } 1565 } 1566 free (update_hard_regno_preference_check); 1567 bitmap_clear (&best_spill_pseudos_bitmap); 1568 bitmap_clear (&spill_pseudos_bitmap); 1569 bitmap_clear (&insn_conflict_pseudos); 1570 return fails_p; 1571 } 1572 1573 /* Entry function to assign hard registers to new reload pseudos 1574 starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling 1575 of old pseudos) and possibly to the old pseudos. The function adds 1576 what insns to process for the next constraint pass. Those are all 1577 insns who contains non-reload and non-inheritance pseudos with 1578 changed allocation. 1579 1580 Return true if we did not spill any non-reload and non-inheritance 1581 pseudos. Set up FAILS_P if we failed to assign hard registers to 1582 all reload pseudos. */ 1583 bool 1584 lra_assign (bool &fails_p) 1585 { 1586 int i; 1587 unsigned int u; 1588 bitmap_iterator bi; 1589 bitmap_head insns_to_process; 1590 bool no_spills_p; 1591 int max_regno = max_reg_num (); 1592 1593 timevar_push (TV_LRA_ASSIGN); 1594 lra_assignment_iter++; 1595 if (lra_dump_file != NULL) 1596 fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n", 1597 lra_assignment_iter); 1598 init_lives (); 1599 sorted_pseudos = XNEWVEC (int, max_regno); 1600 sorted_reload_pseudos = XNEWVEC (int, max_regno); 1601 regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno); 1602 regno_live_length = XNEWVEC (int, max_regno); 1603 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1604 { 1605 int l; 1606 lra_live_range_t r; 1607 1608 regno_allocno_class_array[i] = lra_get_allocno_class (i); 1609 for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 1610 l += r->finish - r->start + 1; 1611 regno_live_length[i] = l; 1612 } 1613 former_reload_pseudo_spill_p = false; 1614 init_regno_assign_info (); 1615 bitmap_initialize (&all_spilled_pseudos, ®_obstack); 1616 create_live_range_start_chains (); 1617 setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos); 1618 if (flag_checking && !flag_ipa_ra) 1619 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1620 if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0 1621 && lra_reg_info[i].call_p 1622 && overlaps_hard_reg_set_p (call_used_reg_set, 1623 PSEUDO_REGNO_MODE (i), reg_renumber[i])) 1624 gcc_unreachable (); 1625 /* Setup insns to process on the next constraint pass. */ 1626 bitmap_initialize (&changed_pseudo_bitmap, ®_obstack); 1627 init_live_reload_and_inheritance_pseudos (); 1628 fails_p = assign_by_spills (); 1629 finish_live_reload_and_inheritance_pseudos (); 1630 bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos); 1631 no_spills_p = true; 1632 EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi) 1633 /* We ignore spilled pseudos created on last inheritance pass 1634 because they will be removed. */ 1635 if (lra_reg_info[u].restore_rtx == NULL_RTX) 1636 { 1637 no_spills_p = false; 1638 break; 1639 } 1640 finish_live_range_start_chains (); 1641 bitmap_clear (&all_spilled_pseudos); 1642 bitmap_initialize (&insns_to_process, ®_obstack); 1643 EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi) 1644 bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap); 1645 bitmap_clear (&changed_pseudo_bitmap); 1646 EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi) 1647 { 1648 lra_push_insn_by_uid (u); 1649 /* Invalidate alternatives for insn should be processed. */ 1650 lra_set_used_insn_alternative_by_uid (u, -1); 1651 } 1652 bitmap_clear (&insns_to_process); 1653 finish_regno_assign_info (); 1654 free (regno_live_length); 1655 free (regno_allocno_class_array); 1656 free (sorted_pseudos); 1657 free (sorted_reload_pseudos); 1658 finish_lives (); 1659 timevar_pop (TV_LRA_ASSIGN); 1660 if (former_reload_pseudo_spill_p) 1661 lra_assignment_iter_after_spill++; 1662 /* This is conditional on flag_checking because valid code can take 1663 more than this maximum number of iteration, but at the same time 1664 the test can uncover errors in machine descriptions. */ 1665 if (flag_checking 1666 && (lra_assignment_iter_after_spill 1667 > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER)) 1668 internal_error 1669 ("Maximum number of LRA assignment passes is achieved (%d)\n", 1670 LRA_MAX_ASSIGNMENT_ITERATION_NUMBER); 1671 return no_spills_p; 1672 } 1673 1674 /* Find start and finish insns for reload pseudo REGNO. Return true 1675 if we managed to find the expected insns. Return false, 1676 otherwise. */ 1677 static bool 1678 find_reload_regno_insns (int regno, rtx_insn * &start, rtx_insn * &finish) 1679 { 1680 unsigned int uid; 1681 bitmap_iterator bi; 1682 int n = 0; 1683 rtx_insn *prev_insn, *next_insn; 1684 rtx_insn *start_insn = NULL, *first_insn = NULL, *second_insn = NULL; 1685 1686 EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi) 1687 { 1688 if (start_insn == NULL) 1689 start_insn = lra_insn_recog_data[uid]->insn; 1690 n++; 1691 } 1692 /* For reload pseudo we should have at most 3 insns referring for it: 1693 input/output reload insns and the original insn. */ 1694 if (n > 3) 1695 return false; 1696 if (n > 1) 1697 { 1698 for (prev_insn = PREV_INSN (start_insn), 1699 next_insn = NEXT_INSN (start_insn); 1700 n != 1 && (prev_insn != NULL || next_insn != NULL); ) 1701 { 1702 if (prev_insn != NULL && first_insn == NULL) 1703 { 1704 if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap, 1705 INSN_UID (prev_insn))) 1706 prev_insn = PREV_INSN (prev_insn); 1707 else 1708 { 1709 first_insn = prev_insn; 1710 n--; 1711 } 1712 } 1713 if (next_insn != NULL && second_insn == NULL) 1714 { 1715 if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap, 1716 INSN_UID (next_insn))) 1717 next_insn = NEXT_INSN (next_insn); 1718 else 1719 { 1720 second_insn = next_insn; 1721 n--; 1722 } 1723 } 1724 } 1725 if (n > 1) 1726 return false; 1727 } 1728 start = first_insn != NULL ? first_insn : start_insn; 1729 finish = second_insn != NULL ? second_insn : start_insn; 1730 return true; 1731 } 1732 1733 /* Process reload pseudos which did not get a hard reg, split a hard 1734 reg live range in live range of a reload pseudo, and then return 1735 TRUE. If we did not split a hard reg live range, report an error, 1736 and return FALSE. */ 1737 bool 1738 lra_split_hard_reg_for (void) 1739 { 1740 int i, regno; 1741 rtx_insn *insn, *first, *last; 1742 unsigned int u; 1743 bitmap_iterator bi; 1744 enum reg_class rclass; 1745 int max_regno = max_reg_num (); 1746 /* We did not assign hard regs to reload pseudos after two 1747 iterations. Either it's an asm and something is wrong with the 1748 constraints, or we have run out of spill registers; error out in 1749 either case. */ 1750 bool asm_p = false; 1751 bitmap_head failed_reload_insns, failed_reload_pseudos; 1752 1753 if (lra_dump_file != NULL) 1754 fprintf (lra_dump_file, 1755 "\n****** Splitting a hard reg after assignment #%d: ******\n\n", 1756 lra_assignment_iter); 1757 bitmap_initialize (&failed_reload_pseudos, ®_obstack); 1758 for (i = lra_constraint_new_regno_start; i < max_regno; i++) 1759 if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0 1760 && (rclass = lra_get_allocno_class (i)) != NO_REGS 1761 && ! bitmap_bit_p (&non_reload_pseudos, i)) 1762 { 1763 if (! find_reload_regno_insns (i, first, last)) 1764 continue; 1765 if (spill_hard_reg_in_range (i, rclass, first, last)) 1766 { 1767 bitmap_clear (&failed_reload_pseudos); 1768 return true; 1769 } 1770 bitmap_set_bit (&failed_reload_pseudos, i); 1771 } 1772 bitmap_initialize (&failed_reload_insns, ®_obstack); 1773 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_pseudos, 0, u, bi) 1774 { 1775 regno = u; 1776 bitmap_ior_into (&failed_reload_insns, 1777 &lra_reg_info[regno].insn_bitmap); 1778 lra_setup_reg_renumber 1779 (regno, ira_class_hard_regs[lra_get_allocno_class (regno)][0], false); 1780 } 1781 EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi) 1782 { 1783 insn = lra_insn_recog_data[u]->insn; 1784 if (asm_noperands (PATTERN (insn)) >= 0) 1785 { 1786 asm_p = true; 1787 error_for_asm (insn, 1788 "%<asm%> operand has impossible constraints"); 1789 /* Avoid further trouble with this insn. 1790 For asm goto, instead of fixing up all the edges 1791 just clear the template and clear input operands 1792 (asm goto doesn't have any output operands). */ 1793 if (JUMP_P (insn)) 1794 { 1795 rtx asm_op = extract_asm_operands (PATTERN (insn)); 1796 ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup (""); 1797 ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0); 1798 ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0); 1799 lra_update_insn_regno_info (insn); 1800 } 1801 else 1802 { 1803 PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx); 1804 lra_set_insn_deleted (insn); 1805 } 1806 } 1807 else if (!asm_p) 1808 { 1809 error ("unable to find a register to spill"); 1810 fatal_insn ("this is the insn:", insn); 1811 } 1812 } 1813 bitmap_clear (&failed_reload_pseudos); 1814 bitmap_clear (&failed_reload_insns); 1815 return false; 1816 } 1817