1 /* Change pseudos by memory. 2 Copyright (C) 2010-2020 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 contains code for a pass to change spilled pseudos into 23 memory. 24 25 The pass creates necessary stack slots and assigns spilled pseudos 26 to the stack slots in following way: 27 28 for all spilled pseudos P most frequently used first do 29 for all stack slots S do 30 if P doesn't conflict with pseudos assigned to S then 31 assign S to P and goto to the next pseudo process 32 end 33 end 34 create new stack slot S and assign P to S 35 end 36 37 The actual algorithm is bit more complicated because of different 38 pseudo sizes. 39 40 After that the code changes spilled pseudos (except ones created 41 from scratches) by corresponding stack slot memory in RTL. 42 43 If at least one stack slot was created, we need to run more passes 44 because we have new addresses which should be checked and because 45 the old address displacements might change and address constraints 46 (or insn memory constraints) might not be satisfied any more. 47 48 For some targets, the pass can spill some pseudos into hard 49 registers of different class (usually into vector registers) 50 instead of spilling them into memory if it is possible and 51 profitable. Spilling GENERAL_REGS pseudo into SSE registers for 52 Intel Corei7 is an example of such optimization. And this is 53 actually recommended by Intel optimization guide. 54 55 The file also contains code for final change of pseudos on hard 56 regs correspondingly assigned to them. */ 57 58 #include "config.h" 59 #include "system.h" 60 #include "coretypes.h" 61 #include "backend.h" 62 #include "target.h" 63 #include "rtl.h" 64 #include "df.h" 65 #include "insn-config.h" 66 #include "regs.h" 67 #include "memmodel.h" 68 #include "ira.h" 69 #include "recog.h" 70 #include "output.h" 71 #include "cfgrtl.h" 72 #include "lra.h" 73 #include "lra-int.h" 74 75 76 /* Max regno at the start of the pass. */ 77 static int regs_num; 78 79 /* Map spilled regno -> hard regno used instead of memory for 80 spilling. */ 81 static rtx *spill_hard_reg; 82 83 /* The structure describes stack slot of a spilled pseudo. */ 84 struct pseudo_slot 85 { 86 /* Number (0, 1, ...) of the stack slot to which given pseudo 87 belongs. */ 88 int slot_num; 89 /* First or next slot with the same slot number. */ 90 struct pseudo_slot *next, *first; 91 /* Memory representing the spilled pseudo. */ 92 rtx mem; 93 }; 94 95 /* The stack slots for each spilled pseudo. Indexed by regnos. */ 96 static struct pseudo_slot *pseudo_slots; 97 98 /* The structure describes a register or a stack slot which can be 99 used for several spilled pseudos. */ 100 class slot 101 { 102 public: 103 /* First pseudo with given stack slot. */ 104 int regno; 105 /* Hard reg into which the slot pseudos are spilled. The value is 106 negative for pseudos spilled into memory. */ 107 int hard_regno; 108 /* Maximum alignment required by all users of the slot. */ 109 unsigned int align; 110 /* Maximum size required by all users of the slot. */ 111 poly_int64 size; 112 /* Memory representing the all stack slot. It can be different from 113 memory representing a pseudo belonging to give stack slot because 114 pseudo can be placed in a part of the corresponding stack slot. 115 The value is NULL for pseudos spilled into a hard reg. */ 116 rtx mem; 117 /* Combined live ranges of all pseudos belonging to given slot. It 118 is used to figure out that a new spilled pseudo can use given 119 stack slot. */ 120 lra_live_range_t live_ranges; 121 }; 122 123 /* Array containing info about the stack slots. The array element is 124 indexed by the stack slot number in the range [0..slots_num). */ 125 static class slot *slots; 126 /* The number of the stack slots currently existing. */ 127 static int slots_num; 128 129 /* Set up memory of the spilled pseudo I. The function can allocate 130 the corresponding stack slot if it is not done yet. */ 131 static void 132 assign_mem_slot (int i) 133 { 134 rtx x = NULL_RTX; 135 machine_mode mode = GET_MODE (regno_reg_rtx[i]); 136 poly_int64 inherent_size = PSEUDO_REGNO_BYTES (i); 137 machine_mode wider_mode 138 = wider_subreg_mode (mode, lra_reg_info[i].biggest_mode); 139 poly_int64 total_size = GET_MODE_SIZE (wider_mode); 140 poly_int64 adjust = 0; 141 142 lra_assert (regno_reg_rtx[i] != NULL_RTX && REG_P (regno_reg_rtx[i]) 143 && lra_reg_info[i].nrefs != 0 && reg_renumber[i] < 0); 144 145 unsigned int slot_num = pseudo_slots[i].slot_num; 146 x = slots[slot_num].mem; 147 if (!x) 148 { 149 x = assign_stack_local (BLKmode, slots[slot_num].size, 150 slots[slot_num].align); 151 slots[slot_num].mem = x; 152 } 153 154 /* On a big endian machine, the "address" of the slot is the address 155 of the low part that fits its inherent mode. */ 156 adjust += subreg_size_lowpart_offset (inherent_size, total_size); 157 x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust); 158 159 /* Set all of the memory attributes as appropriate for a spill. */ 160 set_mem_attrs_for_spill (x); 161 pseudo_slots[i].mem = x; 162 } 163 164 /* Sort pseudos according their usage frequencies. */ 165 static int 166 regno_freq_compare (const void *v1p, const void *v2p) 167 { 168 const int regno1 = *(const int *) v1p; 169 const int regno2 = *(const int *) v2p; 170 int diff; 171 172 if ((diff = lra_reg_info[regno2].freq - lra_reg_info[regno1].freq) != 0) 173 return diff; 174 return regno1 - regno2; 175 } 176 177 /* Sort pseudos according to their slots, putting the slots in the order 178 that they should be allocated. 179 180 First prefer to group slots with variable sizes together and slots 181 with constant sizes together, since that usually makes them easier 182 to address from a common anchor point. E.g. loads of polynomial-sized 183 registers tend to take polynomial offsets while loads of constant-sized 184 registers tend to take constant (non-polynomial) offsets. 185 186 Next, slots with lower numbers have the highest priority and should 187 get the smallest displacement from the stack or frame pointer 188 (whichever is being used). 189 190 The first allocated slot is always closest to the frame pointer, 191 so prefer lower slot numbers when frame_pointer_needed. If the stack 192 and frame grow in the same direction, then the first allocated slot is 193 always closest to the initial stack pointer and furthest away from the 194 final stack pointer, so allocate higher numbers first when using the 195 stack pointer in that case. The reverse is true if the stack and 196 frame grow in opposite directions. */ 197 static int 198 pseudo_reg_slot_compare (const void *v1p, const void *v2p) 199 { 200 const int regno1 = *(const int *) v1p; 201 const int regno2 = *(const int *) v2p; 202 int diff, slot_num1, slot_num2; 203 204 slot_num1 = pseudo_slots[regno1].slot_num; 205 slot_num2 = pseudo_slots[regno2].slot_num; 206 diff = (int (slots[slot_num1].size.is_constant ()) 207 - int (slots[slot_num2].size.is_constant ())); 208 if (diff != 0) 209 return diff; 210 if ((diff = slot_num1 - slot_num2) != 0) 211 return (frame_pointer_needed 212 || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff); 213 poly_int64 total_size1 = GET_MODE_SIZE (lra_reg_info[regno1].biggest_mode); 214 poly_int64 total_size2 = GET_MODE_SIZE (lra_reg_info[regno2].biggest_mode); 215 if ((diff = compare_sizes_for_sort (total_size2, total_size1)) != 0) 216 return diff; 217 return regno1 - regno2; 218 } 219 220 /* Assign spill hard registers to N pseudos in PSEUDO_REGNOS which is 221 sorted in order of highest frequency first. Put the pseudos which 222 did not get a spill hard register at the beginning of array 223 PSEUDO_REGNOS. Return the number of such pseudos. */ 224 static int 225 assign_spill_hard_regs (int *pseudo_regnos, int n) 226 { 227 int i, k, p, regno, res, spill_class_size, hard_regno, nr; 228 enum reg_class rclass, spill_class; 229 machine_mode mode; 230 lra_live_range_t r; 231 rtx_insn *insn; 232 rtx set; 233 basic_block bb; 234 HARD_REG_SET conflict_hard_regs; 235 bitmap setjump_crosses = regstat_get_setjmp_crosses (); 236 /* Hard registers which cannot be used for any purpose at given 237 program point because they are unallocatable or already allocated 238 for other pseudos. */ 239 HARD_REG_SET *reserved_hard_regs; 240 241 if (! lra_reg_spill_p) 242 return n; 243 /* Set up reserved hard regs for every program point. */ 244 reserved_hard_regs = XNEWVEC (HARD_REG_SET, lra_live_max_point); 245 for (p = 0; p < lra_live_max_point; p++) 246 reserved_hard_regs[p] = lra_no_alloc_regs; 247 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++) 248 if (lra_reg_info[i].nrefs != 0 249 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0) 250 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 251 for (p = r->start; p <= r->finish; p++) 252 add_to_hard_reg_set (&reserved_hard_regs[p], 253 lra_reg_info[i].biggest_mode, hard_regno); 254 auto_bitmap ok_insn_bitmap (®_obstack); 255 FOR_EACH_BB_FN (bb, cfun) 256 FOR_BB_INSNS (bb, insn) 257 if (DEBUG_INSN_P (insn) 258 || ((set = single_set (insn)) != NULL_RTX 259 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))) 260 bitmap_set_bit (ok_insn_bitmap, INSN_UID (insn)); 261 for (res = i = 0; i < n; i++) 262 { 263 regno = pseudo_regnos[i]; 264 rclass = lra_get_allocno_class (regno); 265 if (bitmap_bit_p (setjump_crosses, regno) 266 || (spill_class 267 = ((enum reg_class) 268 targetm.spill_class ((reg_class_t) rclass, 269 PSEUDO_REGNO_MODE (regno)))) == NO_REGS 270 || bitmap_intersect_compl_p (&lra_reg_info[regno].insn_bitmap, 271 ok_insn_bitmap)) 272 { 273 pseudo_regnos[res++] = regno; 274 continue; 275 } 276 lra_assert (spill_class != NO_REGS); 277 conflict_hard_regs = lra_reg_info[regno].conflict_hard_regs; 278 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 279 for (p = r->start; p <= r->finish; p++) 280 conflict_hard_regs |= reserved_hard_regs[p]; 281 spill_class_size = ira_class_hard_regs_num[spill_class]; 282 mode = lra_reg_info[regno].biggest_mode; 283 for (k = 0; k < spill_class_size; k++) 284 { 285 hard_regno = ira_class_hard_regs[spill_class][k]; 286 if (TEST_HARD_REG_BIT (eliminable_regset, hard_regno) 287 || !targetm.hard_regno_mode_ok (hard_regno, mode)) 288 continue; 289 if (! overlaps_hard_reg_set_p (conflict_hard_regs, mode, hard_regno)) 290 break; 291 } 292 if (k >= spill_class_size) 293 { 294 /* There is no available regs -- assign memory later. */ 295 pseudo_regnos[res++] = regno; 296 continue; 297 } 298 if (lra_dump_file != NULL) 299 fprintf (lra_dump_file, " Spill r%d into hr%d\n", regno, hard_regno); 300 add_to_hard_reg_set (&hard_regs_spilled_into, 301 lra_reg_info[regno].biggest_mode, hard_regno); 302 /* Update reserved_hard_regs. */ 303 for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next) 304 for (p = r->start; p <= r->finish; p++) 305 add_to_hard_reg_set (&reserved_hard_regs[p], 306 lra_reg_info[regno].biggest_mode, hard_regno); 307 spill_hard_reg[regno] 308 = gen_raw_REG (PSEUDO_REGNO_MODE (regno), hard_regno); 309 for (nr = 0; 310 nr < hard_regno_nregs (hard_regno, 311 lra_reg_info[regno].biggest_mode); 312 nr++) 313 /* Just loop. */ 314 df_set_regs_ever_live (hard_regno + nr, true); 315 } 316 free (reserved_hard_regs); 317 return res; 318 } 319 320 /* Add pseudo REGNO to slot SLOT_NUM. */ 321 static void 322 add_pseudo_to_slot (int regno, int slot_num) 323 { 324 struct pseudo_slot *first; 325 326 /* Each pseudo has an inherent size which comes from its own mode, 327 and a total size which provides room for paradoxical subregs. 328 We need to make sure the size and alignment of the slot are 329 sufficient for both. */ 330 machine_mode mode = wider_subreg_mode (PSEUDO_REGNO_MODE (regno), 331 lra_reg_info[regno].biggest_mode); 332 unsigned int align = spill_slot_alignment (mode); 333 slots[slot_num].align = MAX (slots[slot_num].align, align); 334 slots[slot_num].size = upper_bound (slots[slot_num].size, 335 GET_MODE_SIZE (mode)); 336 337 if (slots[slot_num].regno < 0) 338 { 339 /* It is the first pseudo in the slot. */ 340 slots[slot_num].regno = regno; 341 pseudo_slots[regno].first = &pseudo_slots[regno]; 342 pseudo_slots[regno].next = NULL; 343 } 344 else 345 { 346 first = pseudo_slots[regno].first = &pseudo_slots[slots[slot_num].regno]; 347 pseudo_slots[regno].next = first->next; 348 first->next = &pseudo_slots[regno]; 349 } 350 pseudo_slots[regno].mem = NULL_RTX; 351 pseudo_slots[regno].slot_num = slot_num; 352 slots[slot_num].live_ranges 353 = lra_merge_live_ranges (slots[slot_num].live_ranges, 354 lra_copy_live_range_list 355 (lra_reg_info[regno].live_ranges)); 356 } 357 358 /* Assign stack slot numbers to pseudos in array PSEUDO_REGNOS of 359 length N. Sort pseudos in PSEUDO_REGNOS for subsequent assigning 360 memory stack slots. */ 361 static void 362 assign_stack_slot_num_and_sort_pseudos (int *pseudo_regnos, int n) 363 { 364 int i, j, regno; 365 366 slots_num = 0; 367 /* Assign stack slot numbers to spilled pseudos, use smaller numbers 368 for most frequently used pseudos. */ 369 for (i = 0; i < n; i++) 370 { 371 regno = pseudo_regnos[i]; 372 if (! flag_ira_share_spill_slots) 373 j = slots_num; 374 else 375 { 376 machine_mode mode 377 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno), 378 lra_reg_info[regno].biggest_mode); 379 for (j = 0; j < slots_num; j++) 380 if (slots[j].hard_regno < 0 381 /* Although it's possible to share slots between modes 382 with constant and non-constant widths, we usually 383 get better spill code by keeping the constant and 384 non-constant areas separate. */ 385 && (GET_MODE_SIZE (mode).is_constant () 386 == slots[j].size.is_constant ()) 387 && ! (lra_intersected_live_ranges_p 388 (slots[j].live_ranges, 389 lra_reg_info[regno].live_ranges))) 390 break; 391 } 392 if (j >= slots_num) 393 { 394 /* New slot. */ 395 slots[j].live_ranges = NULL; 396 slots[j].size = 0; 397 slots[j].align = BITS_PER_UNIT; 398 slots[j].regno = slots[j].hard_regno = -1; 399 slots[j].mem = NULL_RTX; 400 slots_num++; 401 } 402 add_pseudo_to_slot (regno, j); 403 } 404 /* Sort regnos according to their slot numbers. */ 405 qsort (pseudo_regnos, n, sizeof (int), pseudo_reg_slot_compare); 406 } 407 408 /* Recursively process LOC in INSN and change spilled pseudos to the 409 corresponding memory or spilled hard reg. Ignore spilled pseudos 410 created from the scratches. Return true if the pseudo nrefs equal 411 to 0 (don't change the pseudo in this case). Otherwise return false. */ 412 static bool 413 remove_pseudos (rtx *loc, rtx_insn *insn) 414 { 415 int i; 416 rtx hard_reg; 417 const char *fmt; 418 enum rtx_code code; 419 bool res = false; 420 421 if (*loc == NULL_RTX) 422 return res; 423 code = GET_CODE (*loc); 424 if (code == SUBREG && REG_P (SUBREG_REG (*loc))) 425 { 426 /* Try to remove memory subregs to simplify LRA job 427 and avoid LRA cycling in case of subreg memory reload. */ 428 res = remove_pseudos (&SUBREG_REG (*loc), insn); 429 if (GET_CODE (SUBREG_REG (*loc)) == MEM) 430 { 431 alter_subreg (loc, false); 432 if (GET_CODE (*loc) == MEM) 433 { 434 lra_get_insn_recog_data (insn)->used_insn_alternative = -1; 435 if (lra_dump_file != NULL) 436 fprintf (lra_dump_file, 437 "Memory subreg was simplified in insn #%u\n", 438 INSN_UID (insn)); 439 } 440 } 441 return res; 442 } 443 else if (code == REG && (i = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER 444 && lra_get_regno_hard_regno (i) < 0 445 /* We do not want to assign memory for former scratches because 446 it might result in an address reload for some targets. In 447 any case we transform such pseudos not getting hard registers 448 into scratches back. */ 449 && ! lra_former_scratch_p (i)) 450 { 451 if (lra_reg_info[i].nrefs == 0 452 && pseudo_slots[i].mem == NULL && spill_hard_reg[i] == NULL) 453 return true; 454 if ((hard_reg = spill_hard_reg[i]) != NULL_RTX) 455 *loc = copy_rtx (hard_reg); 456 else 457 { 458 rtx x = lra_eliminate_regs_1 (insn, pseudo_slots[i].mem, 459 GET_MODE (pseudo_slots[i].mem), 460 false, false, 0, true); 461 *loc = x != pseudo_slots[i].mem ? x : copy_rtx (x); 462 } 463 return res; 464 } 465 466 fmt = GET_RTX_FORMAT (code); 467 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 468 { 469 if (fmt[i] == 'e') 470 res = remove_pseudos (&XEXP (*loc, i), insn) || res; 471 else if (fmt[i] == 'E') 472 { 473 int j; 474 475 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--) 476 res = remove_pseudos (&XVECEXP (*loc, i, j), insn) || res; 477 } 478 } 479 return res; 480 } 481 482 /* Convert spilled pseudos into their stack slots or spill hard regs, 483 put insns to process on the constraint stack (that is all insns in 484 which pseudos were changed to memory or spill hard regs). */ 485 static void 486 spill_pseudos (void) 487 { 488 basic_block bb; 489 rtx_insn *insn, *curr; 490 int i; 491 492 auto_bitmap spilled_pseudos (®_obstack); 493 auto_bitmap changed_insns (®_obstack); 494 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++) 495 { 496 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0 497 && ! lra_former_scratch_p (i)) 498 { 499 bitmap_set_bit (spilled_pseudos, i); 500 bitmap_ior_into (changed_insns, &lra_reg_info[i].insn_bitmap); 501 } 502 } 503 FOR_EACH_BB_FN (bb, cfun) 504 { 505 FOR_BB_INSNS_SAFE (bb, insn, curr) 506 { 507 bool removed_pseudo_p = false; 508 509 if (bitmap_bit_p (changed_insns, INSN_UID (insn))) 510 { 511 rtx *link_loc, link; 512 513 removed_pseudo_p = remove_pseudos (&PATTERN (insn), insn); 514 if (CALL_P (insn) 515 && remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn)) 516 removed_pseudo_p = true; 517 for (link_loc = ®_NOTES (insn); 518 (link = *link_loc) != NULL_RTX; 519 link_loc = &XEXP (link, 1)) 520 { 521 switch (REG_NOTE_KIND (link)) 522 { 523 case REG_FRAME_RELATED_EXPR: 524 case REG_CFA_DEF_CFA: 525 case REG_CFA_ADJUST_CFA: 526 case REG_CFA_OFFSET: 527 case REG_CFA_REGISTER: 528 case REG_CFA_EXPRESSION: 529 case REG_CFA_RESTORE: 530 case REG_CFA_SET_VDRAP: 531 if (remove_pseudos (&XEXP (link, 0), insn)) 532 removed_pseudo_p = true; 533 break; 534 default: 535 break; 536 } 537 } 538 if (lra_dump_file != NULL) 539 fprintf (lra_dump_file, 540 "Changing spilled pseudos to memory in insn #%u\n", 541 INSN_UID (insn)); 542 lra_push_insn (insn); 543 if (lra_reg_spill_p || targetm.different_addr_displacement_p ()) 544 lra_set_used_insn_alternative (insn, LRA_UNKNOWN_ALT); 545 } 546 else if (CALL_P (insn) 547 /* Presence of any pseudo in CALL_INSN_FUNCTION_USAGE 548 does not affect value of insn_bitmap of the 549 corresponding lra_reg_info. That is because we 550 don't need to reload pseudos in 551 CALL_INSN_FUNCTION_USAGEs. So if we process only 552 insns in the insn_bitmap of given pseudo here, we 553 can miss the pseudo in some 554 CALL_INSN_FUNCTION_USAGEs. */ 555 && remove_pseudos (&CALL_INSN_FUNCTION_USAGE (insn), insn)) 556 removed_pseudo_p = true; 557 if (removed_pseudo_p) 558 { 559 lra_assert (DEBUG_INSN_P (insn)); 560 lra_invalidate_insn_data (insn); 561 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); 562 if (lra_dump_file != NULL) 563 fprintf (lra_dump_file, 564 "Debug insn #%u is reset because it referenced " 565 "removed pseudo\n", INSN_UID (insn)); 566 } 567 bitmap_and_compl_into (df_get_live_in (bb), spilled_pseudos); 568 bitmap_and_compl_into (df_get_live_out (bb), spilled_pseudos); 569 } 570 } 571 } 572 573 /* Return true if we need scratch reg assignments. */ 574 bool 575 lra_need_for_scratch_reg_p (void) 576 { 577 int i; max_regno = max_reg_num (); 578 579 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 580 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0 581 && lra_former_scratch_p (i)) 582 return true; 583 return false; 584 } 585 586 /* Return true if we need to change some pseudos into memory. */ 587 bool 588 lra_need_for_spills_p (void) 589 { 590 int i; max_regno = max_reg_num (); 591 592 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 593 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0 594 && ! lra_former_scratch_p (i)) 595 return true; 596 return false; 597 } 598 599 /* Change spilled pseudos into memory or spill hard regs. Put changed 600 insns on the constraint stack (these insns will be considered on 601 the next constraint pass). The changed insns are all insns in 602 which pseudos were changed. */ 603 void 604 lra_spill (void) 605 { 606 int i, n, curr_regno; 607 int *pseudo_regnos; 608 609 regs_num = max_reg_num (); 610 spill_hard_reg = XNEWVEC (rtx, regs_num); 611 pseudo_regnos = XNEWVEC (int, regs_num); 612 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < regs_num; i++) 613 if (lra_reg_info[i].nrefs != 0 && lra_get_regno_hard_regno (i) < 0 614 /* We do not want to assign memory for former scratches. */ 615 && ! lra_former_scratch_p (i)) 616 pseudo_regnos[n++] = i; 617 lra_assert (n > 0); 618 pseudo_slots = XNEWVEC (struct pseudo_slot, regs_num); 619 for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++) 620 { 621 spill_hard_reg[i] = NULL_RTX; 622 pseudo_slots[i].mem = NULL_RTX; 623 } 624 slots = XNEWVEC (class slot, regs_num); 625 /* Sort regnos according their usage frequencies. */ 626 qsort (pseudo_regnos, n, sizeof (int), regno_freq_compare); 627 n = assign_spill_hard_regs (pseudo_regnos, n); 628 assign_stack_slot_num_and_sort_pseudos (pseudo_regnos, n); 629 for (i = 0; i < n; i++) 630 if (pseudo_slots[pseudo_regnos[i]].mem == NULL_RTX) 631 assign_mem_slot (pseudo_regnos[i]); 632 if (n > 0 && crtl->stack_alignment_needed) 633 /* If we have a stack frame, we must align it now. The stack size 634 may be a part of the offset computation for register 635 elimination. */ 636 assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed); 637 if (lra_dump_file != NULL) 638 { 639 for (i = 0; i < slots_num; i++) 640 { 641 fprintf (lra_dump_file, " Slot %d regnos (width = ", i); 642 print_dec (GET_MODE_SIZE (GET_MODE (slots[i].mem)), 643 lra_dump_file, SIGNED); 644 fprintf (lra_dump_file, "):"); 645 for (curr_regno = slots[i].regno;; 646 curr_regno = pseudo_slots[curr_regno].next - pseudo_slots) 647 { 648 fprintf (lra_dump_file, " %d", curr_regno); 649 if (pseudo_slots[curr_regno].next == NULL) 650 break; 651 } 652 fprintf (lra_dump_file, "\n"); 653 } 654 } 655 spill_pseudos (); 656 free (slots); 657 free (pseudo_slots); 658 free (pseudo_regnos); 659 free (spill_hard_reg); 660 } 661 662 /* Apply alter_subreg for subregs of regs in *LOC. Use FINAL_P for 663 alter_subreg calls. Return true if any subreg of reg is 664 processed. */ 665 static bool 666 alter_subregs (rtx *loc, bool final_p) 667 { 668 int i; 669 rtx x = *loc; 670 bool res; 671 const char *fmt; 672 enum rtx_code code; 673 674 if (x == NULL_RTX) 675 return false; 676 code = GET_CODE (x); 677 if (code == SUBREG && REG_P (SUBREG_REG (x))) 678 { 679 lra_assert (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER); 680 alter_subreg (loc, final_p); 681 return true; 682 } 683 fmt = GET_RTX_FORMAT (code); 684 res = false; 685 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 686 { 687 if (fmt[i] == 'e') 688 { 689 if (alter_subregs (&XEXP (x, i), final_p)) 690 res = true; 691 } 692 else if (fmt[i] == 'E') 693 { 694 int j; 695 696 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 697 if (alter_subregs (&XVECEXP (x, i, j), final_p)) 698 res = true; 699 } 700 } 701 return res; 702 } 703 704 /* Return true if REGNO is used for return in the current 705 function. */ 706 static bool 707 return_regno_p (unsigned int regno) 708 { 709 rtx outgoing = crtl->return_rtx; 710 711 if (! outgoing) 712 return false; 713 714 if (REG_P (outgoing)) 715 return REGNO (outgoing) == regno; 716 else if (GET_CODE (outgoing) == PARALLEL) 717 { 718 int i; 719 720 for (i = 0; i < XVECLEN (outgoing, 0); i++) 721 { 722 rtx x = XEXP (XVECEXP (outgoing, 0, i), 0); 723 724 if (REG_P (x) && REGNO (x) == regno) 725 return true; 726 } 727 } 728 return false; 729 } 730 731 /* Return true if REGNO is in one of subsequent USE after INSN in the 732 same BB. */ 733 static bool 734 regno_in_use_p (rtx_insn *insn, unsigned int regno) 735 { 736 static lra_insn_recog_data_t id; 737 static struct lra_static_insn_data *static_id; 738 struct lra_insn_reg *reg; 739 int i, arg_regno; 740 basic_block bb = BLOCK_FOR_INSN (insn); 741 742 while ((insn = next_nondebug_insn (insn)) != NULL_RTX) 743 { 744 if (BARRIER_P (insn) || bb != BLOCK_FOR_INSN (insn)) 745 return false; 746 if (! INSN_P (insn)) 747 continue; 748 if (GET_CODE (PATTERN (insn)) == USE 749 && REG_P (XEXP (PATTERN (insn), 0)) 750 && regno == REGNO (XEXP (PATTERN (insn), 0))) 751 return true; 752 /* Check that the regno is not modified. */ 753 id = lra_get_insn_recog_data (insn); 754 for (reg = id->regs; reg != NULL; reg = reg->next) 755 if (reg->type != OP_IN && reg->regno == (int) regno) 756 return false; 757 static_id = id->insn_static_data; 758 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next) 759 if (reg->type != OP_IN && reg->regno == (int) regno) 760 return false; 761 if (id->arg_hard_regs != NULL) 762 for (i = 0; (arg_regno = id->arg_hard_regs[i]) >= 0; i++) 763 if ((int) regno == (arg_regno >= FIRST_PSEUDO_REGISTER 764 ? arg_regno : arg_regno - FIRST_PSEUDO_REGISTER)) 765 return false; 766 } 767 return false; 768 } 769 770 /* Final change of pseudos got hard registers into the corresponding 771 hard registers and removing temporary clobbers. */ 772 void 773 lra_final_code_change (void) 774 { 775 int i, hard_regno; 776 basic_block bb; 777 rtx_insn *insn, *curr; 778 rtx set; 779 int max_regno = max_reg_num (); 780 781 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 782 if (lra_reg_info[i].nrefs != 0 783 && (hard_regno = lra_get_regno_hard_regno (i)) >= 0) 784 SET_REGNO (regno_reg_rtx[i], hard_regno); 785 FOR_EACH_BB_FN (bb, cfun) 786 FOR_BB_INSNS_SAFE (bb, insn, curr) 787 if (INSN_P (insn)) 788 { 789 rtx pat = PATTERN (insn); 790 791 if (GET_CODE (pat) == CLOBBER && LRA_TEMP_CLOBBER_P (pat)) 792 { 793 /* Remove clobbers temporarily created in LRA. We don't 794 need them anymore and don't want to waste compiler 795 time processing them in a few subsequent passes. */ 796 lra_invalidate_insn_data (insn); 797 delete_insn (insn); 798 continue; 799 } 800 801 /* IRA can generate move insns involving pseudos. It is 802 better remove them earlier to speed up compiler a bit. 803 It is also better to do it here as they might not pass 804 final RTL check in LRA, (e.g. insn moving a control 805 register into itself). So remove an useless move insn 806 unless next insn is USE marking the return reg (we should 807 save this as some subsequent optimizations assume that 808 such original insns are saved). */ 809 if (NONJUMP_INSN_P (insn) && GET_CODE (pat) == SET 810 && REG_P (SET_SRC (pat)) && REG_P (SET_DEST (pat)) 811 && REGNO (SET_SRC (pat)) == REGNO (SET_DEST (pat)) 812 && (! return_regno_p (REGNO (SET_SRC (pat))) 813 || ! regno_in_use_p (insn, REGNO (SET_SRC (pat))))) 814 { 815 lra_invalidate_insn_data (insn); 816 delete_insn (insn); 817 continue; 818 } 819 820 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 821 struct lra_insn_reg *reg; 822 823 for (reg = id->regs; reg != NULL; reg = reg->next) 824 if (reg->regno >= FIRST_PSEUDO_REGISTER 825 && lra_reg_info [reg->regno].nrefs == 0) 826 break; 827 828 if (reg != NULL) 829 { 830 /* Pseudos still can be in debug insns in some very rare 831 and complicated cases, e.g. the pseudo was removed by 832 inheritance and the debug insn is not EBBs where the 833 inheritance happened. It is difficult and time 834 consuming to find what hard register corresponds the 835 pseudo -- so just remove the debug insn. Another 836 solution could be assigning hard reg/memory but it 837 would be a misleading info. It is better not to have 838 info than have it wrong. */ 839 lra_assert (DEBUG_INSN_P (insn)); 840 lra_invalidate_insn_data (insn); 841 delete_insn (insn); 842 continue; 843 } 844 845 struct lra_static_insn_data *static_id = id->insn_static_data; 846 bool insn_change_p = false; 847 848 for (i = id->insn_static_data->n_operands - 1; i >= 0; i--) 849 if ((DEBUG_INSN_P (insn) || ! static_id->operand[i].is_operator) 850 && alter_subregs (id->operand_loc[i], ! DEBUG_INSN_P (insn))) 851 { 852 lra_update_dup (id, i); 853 insn_change_p = true; 854 } 855 if (insn_change_p) 856 lra_update_operator_dups (id); 857 858 if ((set = single_set (insn)) != NULL 859 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)) 860 && REGNO (SET_SRC (set)) == REGNO (SET_DEST (set))) 861 { 862 /* Remove an useless move insn. IRA can generate move 863 insns involving pseudos. It is better remove them 864 earlier to speed up compiler a bit. It is also 865 better to do it here as they might not pass final RTL 866 check in LRA, (e.g. insn moving a control register 867 into itself). */ 868 lra_invalidate_insn_data (insn); 869 delete_insn (insn); 870 } 871 } 872 } 873