1 /* IRA processing allocno lives to build allocno live ranges. 2 Copyright (C) 2006-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 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "target.h" 26 #include "rtl.h" 27 #include "predict.h" 28 #include "df.h" 29 #include "memmodel.h" 30 #include "tm_p.h" 31 #include "insn-config.h" 32 #include "regs.h" 33 #include "ira.h" 34 #include "ira-int.h" 35 #include "sparseset.h" 36 37 /* The code in this file is similar to one in global but the code 38 works on the allocno basis and creates live ranges instead of 39 pseudo-register conflicts. */ 40 41 /* Program points are enumerated by numbers from range 42 0..IRA_MAX_POINT-1. There are approximately two times more program 43 points than insns. Program points are places in the program where 44 liveness info can be changed. In most general case (there are more 45 complicated cases too) some program points correspond to places 46 where input operand dies and other ones correspond to places where 47 output operands are born. */ 48 int ira_max_point; 49 50 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno 51 live ranges with given start/finish point. */ 52 live_range_t *ira_start_point_ranges, *ira_finish_point_ranges; 53 54 /* Number of the current program point. */ 55 static int curr_point; 56 57 /* Point where register pressure excess started or -1 if there is no 58 register pressure excess. Excess pressure for a register class at 59 some point means that there are more allocnos of given register 60 class living at the point than number of hard-registers of the 61 class available for the allocation. It is defined only for 62 pressure classes. */ 63 static int high_pressure_start_point[N_REG_CLASSES]; 64 65 /* Objects live at current point in the scan. */ 66 static sparseset objects_live; 67 68 /* A temporary bitmap used in functions that wish to avoid visiting an allocno 69 multiple times. */ 70 static sparseset allocnos_processed; 71 72 /* Set of hard regs (except eliminable ones) currently live. */ 73 static HARD_REG_SET hard_regs_live; 74 75 /* The loop tree node corresponding to the current basic block. */ 76 static ira_loop_tree_node_t curr_bb_node; 77 78 /* The number of the last processed call. */ 79 static int last_call_num; 80 /* The number of last call at which given allocno was saved. */ 81 static int *allocno_saved_at_call; 82 83 /* The value of get_preferred_alternatives for the current instruction, 84 supplemental to recog_data. */ 85 static alternative_mask preferred_alternatives; 86 87 /* Record the birth of hard register REGNO, updating hard_regs_live and 88 hard reg conflict information for living allocnos. */ 89 static void 90 make_hard_regno_born (int regno) 91 { 92 unsigned int i; 93 94 SET_HARD_REG_BIT (hard_regs_live, regno); 95 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i) 96 { 97 ira_object_t obj = ira_object_id_map[i]; 98 99 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno); 100 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno); 101 } 102 } 103 104 /* Process the death of hard register REGNO. This updates 105 hard_regs_live. */ 106 static void 107 make_hard_regno_dead (int regno) 108 { 109 CLEAR_HARD_REG_BIT (hard_regs_live, regno); 110 } 111 112 /* Record the birth of object OBJ. Set a bit for it in objects_live, 113 start a new live range for it if necessary and update hard register 114 conflicts. */ 115 static void 116 make_object_born (ira_object_t obj) 117 { 118 live_range_t lr = OBJECT_LIVE_RANGES (obj); 119 120 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj)); 121 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), hard_regs_live); 122 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), hard_regs_live); 123 124 if (lr == NULL 125 || (lr->finish != curr_point && lr->finish + 1 != curr_point)) 126 ira_add_live_range_to_object (obj, curr_point, -1); 127 } 128 129 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno 130 associated with object OBJ. */ 131 static void 132 update_allocno_pressure_excess_length (ira_object_t obj) 133 { 134 ira_allocno_t a = OBJECT_ALLOCNO (obj); 135 int start, i; 136 enum reg_class aclass, pclass, cl; 137 live_range_t p; 138 139 aclass = ALLOCNO_CLASS (a); 140 pclass = ira_pressure_class_translate[aclass]; 141 for (i = 0; 142 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES; 143 i++) 144 { 145 if (! ira_reg_pressure_class_p[cl]) 146 continue; 147 if (high_pressure_start_point[cl] < 0) 148 continue; 149 p = OBJECT_LIVE_RANGES (obj); 150 ira_assert (p != NULL); 151 start = (high_pressure_start_point[cl] > p->start 152 ? high_pressure_start_point[cl] : p->start); 153 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1; 154 } 155 } 156 157 /* Process the death of object OBJ, which is associated with allocno 158 A. This finishes the current live range for it. */ 159 static void 160 make_object_dead (ira_object_t obj) 161 { 162 live_range_t lr; 163 164 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (obj)); 165 lr = OBJECT_LIVE_RANGES (obj); 166 ira_assert (lr != NULL); 167 lr->finish = curr_point; 168 update_allocno_pressure_excess_length (obj); 169 } 170 171 /* The current register pressures for each pressure class for the current 172 basic block. */ 173 static int curr_reg_pressure[N_REG_CLASSES]; 174 175 /* Record that register pressure for PCLASS increased by N registers. 176 Update the current register pressure, maximal register pressure for 177 the current BB and the start point of the register pressure 178 excess. */ 179 static void 180 inc_register_pressure (enum reg_class pclass, int n) 181 { 182 int i; 183 enum reg_class cl; 184 185 for (i = 0; 186 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES; 187 i++) 188 { 189 if (! ira_reg_pressure_class_p[cl]) 190 continue; 191 curr_reg_pressure[cl] += n; 192 if (high_pressure_start_point[cl] < 0 193 && (curr_reg_pressure[cl] > ira_class_hard_regs_num[cl])) 194 high_pressure_start_point[cl] = curr_point; 195 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl]) 196 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl]; 197 } 198 } 199 200 /* Record that register pressure for PCLASS has decreased by NREGS 201 registers; update current register pressure, start point of the 202 register pressure excess, and register pressure excess length for 203 living allocnos. */ 204 205 static void 206 dec_register_pressure (enum reg_class pclass, int nregs) 207 { 208 int i; 209 unsigned int j; 210 enum reg_class cl; 211 bool set_p = false; 212 213 for (i = 0; 214 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES; 215 i++) 216 { 217 if (! ira_reg_pressure_class_p[cl]) 218 continue; 219 curr_reg_pressure[cl] -= nregs; 220 ira_assert (curr_reg_pressure[cl] >= 0); 221 if (high_pressure_start_point[cl] >= 0 222 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl]) 223 set_p = true; 224 } 225 if (set_p) 226 { 227 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j) 228 update_allocno_pressure_excess_length (ira_object_id_map[j]); 229 for (i = 0; 230 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES; 231 i++) 232 { 233 if (! ira_reg_pressure_class_p[cl]) 234 continue; 235 if (high_pressure_start_point[cl] >= 0 236 && curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl]) 237 high_pressure_start_point[cl] = -1; 238 } 239 } 240 } 241 242 /* Determine from the objects_live bitmap whether REGNO is currently live, 243 and occupies only one object. Return false if we have no information. */ 244 static bool 245 pseudo_regno_single_word_and_live_p (int regno) 246 { 247 ira_allocno_t a = ira_curr_regno_allocno_map[regno]; 248 ira_object_t obj; 249 250 if (a == NULL) 251 return false; 252 if (ALLOCNO_NUM_OBJECTS (a) > 1) 253 return false; 254 255 obj = ALLOCNO_OBJECT (a, 0); 256 257 return sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)); 258 } 259 260 /* Mark the pseudo register REGNO as live. Update all information about 261 live ranges and register pressure. */ 262 static void 263 mark_pseudo_regno_live (int regno) 264 { 265 ira_allocno_t a = ira_curr_regno_allocno_map[regno]; 266 enum reg_class pclass; 267 int i, n, nregs; 268 269 if (a == NULL) 270 return; 271 272 /* Invalidate because it is referenced. */ 273 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0; 274 275 n = ALLOCNO_NUM_OBJECTS (a); 276 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)]; 277 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]; 278 if (n > 1) 279 { 280 /* We track every subobject separately. */ 281 gcc_assert (nregs == n); 282 nregs = 1; 283 } 284 285 for (i = 0; i < n; i++) 286 { 287 ira_object_t obj = ALLOCNO_OBJECT (a, i); 288 289 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj))) 290 continue; 291 292 inc_register_pressure (pclass, nregs); 293 make_object_born (obj); 294 } 295 } 296 297 /* Like mark_pseudo_regno_live, but try to only mark one subword of 298 the pseudo as live. SUBWORD indicates which; a value of 0 299 indicates the low part. */ 300 static void 301 mark_pseudo_regno_subword_live (int regno, int subword) 302 { 303 ira_allocno_t a = ira_curr_regno_allocno_map[regno]; 304 int n; 305 enum reg_class pclass; 306 ira_object_t obj; 307 308 if (a == NULL) 309 return; 310 311 /* Invalidate because it is referenced. */ 312 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0; 313 314 n = ALLOCNO_NUM_OBJECTS (a); 315 if (n == 1) 316 { 317 mark_pseudo_regno_live (regno); 318 return; 319 } 320 321 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)]; 322 gcc_assert 323 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]); 324 obj = ALLOCNO_OBJECT (a, subword); 325 326 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj))) 327 return; 328 329 inc_register_pressure (pclass, 1); 330 make_object_born (obj); 331 } 332 333 /* Mark the register REG as live. Store a 1 in hard_regs_live for 334 this register, record how many consecutive hardware registers it 335 actually needs. */ 336 static void 337 mark_hard_reg_live (rtx reg) 338 { 339 int regno = REGNO (reg); 340 341 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)) 342 { 343 int last = END_REGNO (reg); 344 enum reg_class aclass, pclass; 345 346 while (regno < last) 347 { 348 if (! TEST_HARD_REG_BIT (hard_regs_live, regno) 349 && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) 350 { 351 aclass = ira_hard_regno_allocno_class[regno]; 352 pclass = ira_pressure_class_translate[aclass]; 353 inc_register_pressure (pclass, 1); 354 make_hard_regno_born (regno); 355 } 356 regno++; 357 } 358 } 359 } 360 361 /* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's 362 register number; ORIG_REG is the access in the insn, which may be a 363 subreg. */ 364 static void 365 mark_pseudo_reg_live (rtx orig_reg, unsigned regno) 366 { 367 if (read_modify_subreg_p (orig_reg)) 368 { 369 mark_pseudo_regno_subword_live (regno, 370 subreg_lowpart_p (orig_reg) ? 0 : 1); 371 } 372 else 373 mark_pseudo_regno_live (regno); 374 } 375 376 /* Mark the register referenced by use or def REF as live. */ 377 static void 378 mark_ref_live (df_ref ref) 379 { 380 rtx reg = DF_REF_REG (ref); 381 rtx orig_reg = reg; 382 383 if (GET_CODE (reg) == SUBREG) 384 reg = SUBREG_REG (reg); 385 386 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER) 387 mark_pseudo_reg_live (orig_reg, REGNO (reg)); 388 else 389 mark_hard_reg_live (reg); 390 } 391 392 /* Mark the pseudo register REGNO as dead. Update all information about 393 live ranges and register pressure. */ 394 static void 395 mark_pseudo_regno_dead (int regno) 396 { 397 ira_allocno_t a = ira_curr_regno_allocno_map[regno]; 398 int n, i, nregs; 399 enum reg_class cl; 400 401 if (a == NULL) 402 return; 403 404 /* Invalidate because it is referenced. */ 405 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0; 406 407 n = ALLOCNO_NUM_OBJECTS (a); 408 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)]; 409 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]; 410 if (n > 1) 411 { 412 /* We track every subobject separately. */ 413 gcc_assert (nregs == n); 414 nregs = 1; 415 } 416 for (i = 0; i < n; i++) 417 { 418 ira_object_t obj = ALLOCNO_OBJECT (a, i); 419 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj))) 420 continue; 421 422 dec_register_pressure (cl, nregs); 423 make_object_dead (obj); 424 } 425 } 426 427 /* Like mark_pseudo_regno_dead, but called when we know that only part of the 428 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */ 429 static void 430 mark_pseudo_regno_subword_dead (int regno, int subword) 431 { 432 ira_allocno_t a = ira_curr_regno_allocno_map[regno]; 433 int n; 434 enum reg_class cl; 435 ira_object_t obj; 436 437 if (a == NULL) 438 return; 439 440 /* Invalidate because it is referenced. */ 441 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0; 442 443 n = ALLOCNO_NUM_OBJECTS (a); 444 if (n == 1) 445 /* The allocno as a whole doesn't die in this case. */ 446 return; 447 448 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)]; 449 gcc_assert 450 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]); 451 452 obj = ALLOCNO_OBJECT (a, subword); 453 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj))) 454 return; 455 456 dec_register_pressure (cl, 1); 457 make_object_dead (obj); 458 } 459 460 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the 461 register. */ 462 static void 463 mark_hard_reg_dead (rtx reg) 464 { 465 int regno = REGNO (reg); 466 467 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)) 468 { 469 int last = END_REGNO (reg); 470 enum reg_class aclass, pclass; 471 472 while (regno < last) 473 { 474 if (TEST_HARD_REG_BIT (hard_regs_live, regno)) 475 { 476 aclass = ira_hard_regno_allocno_class[regno]; 477 pclass = ira_pressure_class_translate[aclass]; 478 dec_register_pressure (pclass, 1); 479 make_hard_regno_dead (regno); 480 } 481 regno++; 482 } 483 } 484 } 485 486 /* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's 487 register number; ORIG_REG is the access in the insn, which may be a 488 subreg. */ 489 static void 490 mark_pseudo_reg_dead (rtx orig_reg, unsigned regno) 491 { 492 if (read_modify_subreg_p (orig_reg)) 493 { 494 mark_pseudo_regno_subword_dead (regno, 495 subreg_lowpart_p (orig_reg) ? 0 : 1); 496 } 497 else 498 mark_pseudo_regno_dead (regno); 499 } 500 501 /* Mark the register referenced by definition DEF as dead, if the 502 definition is a total one. */ 503 static void 504 mark_ref_dead (df_ref def) 505 { 506 rtx reg = DF_REF_REG (def); 507 rtx orig_reg = reg; 508 509 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)) 510 return; 511 512 if (GET_CODE (reg) == SUBREG) 513 reg = SUBREG_REG (reg); 514 515 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL) 516 && (GET_CODE (orig_reg) != SUBREG 517 || REGNO (reg) < FIRST_PSEUDO_REGISTER 518 || !read_modify_subreg_p (orig_reg))) 519 return; 520 521 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER) 522 mark_pseudo_reg_dead (orig_reg, REGNO (reg)); 523 else 524 mark_hard_reg_dead (reg); 525 } 526 527 /* If REG is a pseudo or a subreg of it, and the class of its allocno 528 intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the 529 rtx actually accessed, it may be identical to DREG or a subreg of it. 530 Advance the current program point before making the conflict if 531 ADVANCE_P. Return TRUE if we will need to advance the current 532 program point. */ 533 static bool 534 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, rtx orig_dreg, 535 bool advance_p) 536 { 537 rtx orig_reg = reg; 538 ira_allocno_t a; 539 540 if (GET_CODE (reg) == SUBREG) 541 reg = SUBREG_REG (reg); 542 543 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER) 544 return advance_p; 545 546 a = ira_curr_regno_allocno_map[REGNO (reg)]; 547 if (! reg_classes_intersect_p (cl, ALLOCNO_CLASS (a))) 548 return advance_p; 549 550 if (advance_p) 551 curr_point++; 552 553 mark_pseudo_reg_live (orig_reg, REGNO (reg)); 554 mark_pseudo_reg_live (orig_dreg, REGNO (dreg)); 555 mark_pseudo_reg_dead (orig_reg, REGNO (reg)); 556 mark_pseudo_reg_dead (orig_dreg, REGNO (dreg)); 557 558 return false; 559 } 560 561 /* Check and make if necessary conflicts for pseudo DREG of class 562 DEF_CL of the current insn with input operand USE of class USE_CL. 563 ORIG_DREG is the rtx actually accessed, it may be identical to 564 DREG or a subreg of it. Advance the current program point before 565 making the conflict if ADVANCE_P. Return TRUE if we will need to 566 advance the current program point. */ 567 static bool 568 check_and_make_def_use_conflict (rtx dreg, rtx orig_dreg, 569 enum reg_class def_cl, int use, 570 enum reg_class use_cl, bool advance_p) 571 { 572 if (! reg_classes_intersect_p (def_cl, use_cl)) 573 return advance_p; 574 575 advance_p = make_pseudo_conflict (recog_data.operand[use], 576 use_cl, dreg, orig_dreg, advance_p); 577 578 /* Reload may end up swapping commutative operands, so you 579 have to take both orderings into account. The 580 constraints for the two operands can be completely 581 different. (Indeed, if the constraints for the two 582 operands are the same for all alternatives, there's no 583 point marking them as commutative.) */ 584 if (use < recog_data.n_operands - 1 585 && recog_data.constraints[use][0] == '%') 586 advance_p 587 = make_pseudo_conflict (recog_data.operand[use + 1], 588 use_cl, dreg, orig_dreg, advance_p); 589 if (use >= 1 590 && recog_data.constraints[use - 1][0] == '%') 591 advance_p 592 = make_pseudo_conflict (recog_data.operand[use - 1], 593 use_cl, dreg, orig_dreg, advance_p); 594 return advance_p; 595 } 596 597 /* Check and make if necessary conflicts for definition DEF of class 598 DEF_CL of the current insn with input operands. Process only 599 constraints of alternative ALT. */ 600 static void 601 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl) 602 { 603 int use, use_match; 604 ira_allocno_t a; 605 enum reg_class use_cl, acl; 606 bool advance_p; 607 rtx dreg = recog_data.operand[def]; 608 rtx orig_dreg = dreg; 609 610 if (def_cl == NO_REGS) 611 return; 612 613 if (GET_CODE (dreg) == SUBREG) 614 dreg = SUBREG_REG (dreg); 615 616 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER) 617 return; 618 619 a = ira_curr_regno_allocno_map[REGNO (dreg)]; 620 acl = ALLOCNO_CLASS (a); 621 if (! reg_classes_intersect_p (acl, def_cl)) 622 return; 623 624 advance_p = true; 625 626 int n_operands = recog_data.n_operands; 627 const operand_alternative *op_alt = &recog_op_alt[alt * n_operands]; 628 for (use = 0; use < n_operands; use++) 629 { 630 int alt1; 631 632 if (use == def || recog_data.operand_type[use] == OP_OUT) 633 continue; 634 635 if (op_alt[use].anything_ok) 636 use_cl = ALL_REGS; 637 else 638 use_cl = op_alt[use].cl; 639 640 /* If there's any alternative that allows USE to match DEF, do not 641 record a conflict. If that causes us to create an invalid 642 instruction due to the earlyclobber, reload must fix it up. */ 643 for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++) 644 { 645 if (!TEST_BIT (preferred_alternatives, alt1)) 646 continue; 647 const operand_alternative *op_alt1 648 = &recog_op_alt[alt1 * n_operands]; 649 if (op_alt1[use].matches == def 650 || (use < n_operands - 1 651 && recog_data.constraints[use][0] == '%' 652 && op_alt1[use + 1].matches == def) 653 || (use >= 1 654 && recog_data.constraints[use - 1][0] == '%' 655 && op_alt1[use - 1].matches == def)) 656 break; 657 } 658 659 if (alt1 < recog_data.n_alternatives) 660 continue; 661 662 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl, 663 use, use_cl, advance_p); 664 665 if ((use_match = op_alt[use].matches) >= 0) 666 { 667 if (use_match == def) 668 continue; 669 670 if (op_alt[use_match].anything_ok) 671 use_cl = ALL_REGS; 672 else 673 use_cl = op_alt[use_match].cl; 674 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl, 675 use, use_cl, advance_p); 676 } 677 } 678 } 679 680 /* Make conflicts of early clobber pseudo registers of the current 681 insn with its inputs. Avoid introducing unnecessary conflicts by 682 checking classes of the constraints and pseudos because otherwise 683 significant code degradation is possible for some targets. */ 684 static void 685 make_early_clobber_and_input_conflicts (void) 686 { 687 int alt; 688 int def, def_match; 689 enum reg_class def_cl; 690 691 int n_alternatives = recog_data.n_alternatives; 692 int n_operands = recog_data.n_operands; 693 const operand_alternative *op_alt = recog_op_alt; 694 for (alt = 0; alt < n_alternatives; alt++, op_alt += n_operands) 695 if (TEST_BIT (preferred_alternatives, alt)) 696 for (def = 0; def < n_operands; def++) 697 { 698 def_cl = NO_REGS; 699 if (op_alt[def].earlyclobber) 700 { 701 if (op_alt[def].anything_ok) 702 def_cl = ALL_REGS; 703 else 704 def_cl = op_alt[def].cl; 705 check_and_make_def_conflict (alt, def, def_cl); 706 } 707 if ((def_match = op_alt[def].matches) >= 0 708 && (op_alt[def_match].earlyclobber 709 || op_alt[def].earlyclobber)) 710 { 711 if (op_alt[def_match].anything_ok) 712 def_cl = ALL_REGS; 713 else 714 def_cl = op_alt[def_match].cl; 715 check_and_make_def_conflict (alt, def, def_cl); 716 } 717 } 718 } 719 720 /* Mark early clobber hard registers of the current INSN as live (if 721 LIVE_P) or dead. Return true if there are such registers. */ 722 static bool 723 mark_hard_reg_early_clobbers (rtx_insn *insn, bool live_p) 724 { 725 df_ref def; 726 bool set_p = false; 727 728 FOR_EACH_INSN_DEF (def, insn) 729 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER)) 730 { 731 rtx dreg = DF_REF_REG (def); 732 733 if (GET_CODE (dreg) == SUBREG) 734 dreg = SUBREG_REG (dreg); 735 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER) 736 continue; 737 738 /* Hard register clobbers are believed to be early clobber 739 because there is no way to say that non-operand hard 740 register clobbers are not early ones. */ 741 if (live_p) 742 mark_ref_live (def); 743 else 744 mark_ref_dead (def); 745 set_p = true; 746 } 747 748 return set_p; 749 } 750 751 /* Checks that CONSTRAINTS permits to use only one hard register. If 752 it is so, the function returns the class of the hard register. 753 Otherwise it returns NO_REGS. */ 754 static enum reg_class 755 single_reg_class (const char *constraints, rtx op, rtx equiv_const) 756 { 757 int c; 758 enum reg_class cl, next_cl; 759 enum constraint_num cn; 760 761 cl = NO_REGS; 762 alternative_mask preferred = preferred_alternatives; 763 for (; (c = *constraints); constraints += CONSTRAINT_LEN (c, constraints)) 764 if (c == '#') 765 preferred &= ~ALTERNATIVE_BIT (0); 766 else if (c == ',') 767 preferred >>= 1; 768 else if (preferred & 1) 769 switch (c) 770 { 771 case 'g': 772 return NO_REGS; 773 774 default: 775 /* ??? Is this the best way to handle memory constraints? */ 776 cn = lookup_constraint (constraints); 777 if (insn_extra_memory_constraint (cn) 778 || insn_extra_special_memory_constraint (cn) 779 || insn_extra_address_constraint (cn)) 780 return NO_REGS; 781 if (constraint_satisfied_p (op, cn) 782 || (equiv_const != NULL_RTX 783 && CONSTANT_P (equiv_const) 784 && constraint_satisfied_p (equiv_const, cn))) 785 return NO_REGS; 786 next_cl = reg_class_for_constraint (cn); 787 if (next_cl == NO_REGS) 788 break; 789 if (cl == NO_REGS 790 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0 791 : (ira_class_singleton[cl][GET_MODE (op)] 792 != ira_class_singleton[next_cl][GET_MODE (op)])) 793 return NO_REGS; 794 cl = next_cl; 795 break; 796 797 case '0': case '1': case '2': case '3': case '4': 798 case '5': case '6': case '7': case '8': case '9': 799 next_cl 800 = single_reg_class (recog_data.constraints[c - '0'], 801 recog_data.operand[c - '0'], NULL_RTX); 802 if (cl == NO_REGS 803 ? ira_class_singleton[next_cl][GET_MODE (op)] < 0 804 : (ira_class_singleton[cl][GET_MODE (op)] 805 != ira_class_singleton[next_cl][GET_MODE (op)])) 806 return NO_REGS; 807 cl = next_cl; 808 break; 809 } 810 return cl; 811 } 812 813 /* The function checks that operand OP_NUM of the current insn can use 814 only one hard register. If it is so, the function returns the 815 class of the hard register. Otherwise it returns NO_REGS. */ 816 static enum reg_class 817 single_reg_operand_class (int op_num) 818 { 819 if (op_num < 0 || recog_data.n_alternatives == 0) 820 return NO_REGS; 821 return single_reg_class (recog_data.constraints[op_num], 822 recog_data.operand[op_num], NULL_RTX); 823 } 824 825 /* The function sets up hard register set *SET to hard registers which 826 might be used by insn reloads because the constraints are too 827 strict. */ 828 void 829 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set, 830 alternative_mask preferred) 831 { 832 int i, c, regno = 0; 833 enum reg_class cl; 834 rtx op; 835 machine_mode mode; 836 837 CLEAR_HARD_REG_SET (*set); 838 for (i = 0; i < recog_data.n_operands; i++) 839 { 840 op = recog_data.operand[i]; 841 842 if (GET_CODE (op) == SUBREG) 843 op = SUBREG_REG (op); 844 845 if (GET_CODE (op) == SCRATCH 846 || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)) 847 { 848 const char *p = recog_data.constraints[i]; 849 850 mode = (GET_CODE (op) == SCRATCH 851 ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno)); 852 cl = NO_REGS; 853 for (; (c = *p); p += CONSTRAINT_LEN (c, p)) 854 if (c == '#') 855 preferred &= ~ALTERNATIVE_BIT (0); 856 else if (c == ',') 857 preferred >>= 1; 858 else if (preferred & 1) 859 { 860 cl = reg_class_for_constraint (lookup_constraint (p)); 861 if (cl != NO_REGS) 862 { 863 /* There is no register pressure problem if all of the 864 regs in this class are fixed. */ 865 int regno = ira_class_singleton[cl][mode]; 866 if (regno >= 0) 867 add_to_hard_reg_set (set, mode, regno); 868 } 869 } 870 } 871 } 872 } 873 /* Processes input operands, if IN_P, or output operands otherwise of 874 the current insn with FREQ to find allocno which can use only one 875 hard register and makes other currently living allocnos conflicting 876 with the hard register. */ 877 static void 878 process_single_reg_class_operands (bool in_p, int freq) 879 { 880 int i, regno; 881 unsigned int px; 882 enum reg_class cl; 883 rtx operand; 884 ira_allocno_t operand_a, a; 885 886 for (i = 0; i < recog_data.n_operands; i++) 887 { 888 operand = recog_data.operand[i]; 889 if (in_p && recog_data.operand_type[i] != OP_IN 890 && recog_data.operand_type[i] != OP_INOUT) 891 continue; 892 if (! in_p && recog_data.operand_type[i] != OP_OUT 893 && recog_data.operand_type[i] != OP_INOUT) 894 continue; 895 cl = single_reg_operand_class (i); 896 if (cl == NO_REGS) 897 continue; 898 899 operand_a = NULL; 900 901 if (GET_CODE (operand) == SUBREG) 902 operand = SUBREG_REG (operand); 903 904 if (REG_P (operand) 905 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER) 906 { 907 enum reg_class aclass; 908 909 operand_a = ira_curr_regno_allocno_map[regno]; 910 aclass = ALLOCNO_CLASS (operand_a); 911 if (ira_class_subset_p[cl][aclass]) 912 { 913 /* View the desired allocation of OPERAND as: 914 915 (REG:YMODE YREGNO), 916 917 a simplification of: 918 919 (subreg:YMODE (reg:XMODE XREGNO) OFFSET). */ 920 machine_mode ymode, xmode; 921 int xregno, yregno; 922 poly_int64 offset; 923 924 xmode = recog_data.operand_mode[i]; 925 xregno = ira_class_singleton[cl][xmode]; 926 gcc_assert (xregno >= 0); 927 ymode = ALLOCNO_MODE (operand_a); 928 offset = subreg_lowpart_offset (ymode, xmode); 929 yregno = simplify_subreg_regno (xregno, xmode, offset, ymode); 930 if (yregno >= 0 931 && ira_class_hard_reg_index[aclass][yregno] >= 0) 932 { 933 int cost; 934 935 ira_allocate_and_set_costs 936 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), 937 aclass, 0); 938 ira_init_register_move_cost_if_necessary (xmode); 939 cost = freq * (in_p 940 ? ira_register_move_cost[xmode][aclass][cl] 941 : ira_register_move_cost[xmode][cl][aclass]); 942 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a) 943 [ira_class_hard_reg_index[aclass][yregno]] -= cost; 944 } 945 } 946 } 947 948 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px) 949 { 950 ira_object_t obj = ira_object_id_map[px]; 951 a = OBJECT_ALLOCNO (obj); 952 if (a != operand_a) 953 { 954 /* We could increase costs of A instead of making it 955 conflicting with the hard register. But it works worse 956 because it will be spilled in reload in anyway. */ 957 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 958 reg_class_contents[cl]); 959 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 960 reg_class_contents[cl]); 961 } 962 } 963 } 964 } 965 966 /* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if 967 we find a SET rtx that we can use to deduce that a register can be cheaply 968 caller-saved. Return such a register, or NULL_RTX if none is found. */ 969 static rtx 970 find_call_crossed_cheap_reg (rtx_insn *insn) 971 { 972 rtx cheap_reg = NULL_RTX; 973 rtx exp = CALL_INSN_FUNCTION_USAGE (insn); 974 975 while (exp != NULL) 976 { 977 rtx x = XEXP (exp, 0); 978 if (GET_CODE (x) == SET) 979 { 980 exp = x; 981 break; 982 } 983 exp = XEXP (exp, 1); 984 } 985 if (exp != NULL) 986 { 987 basic_block bb = BLOCK_FOR_INSN (insn); 988 rtx reg = SET_SRC (exp); 989 rtx_insn *prev = PREV_INSN (insn); 990 while (prev && !(INSN_P (prev) 991 && BLOCK_FOR_INSN (prev) != bb)) 992 { 993 if (NONDEBUG_INSN_P (prev)) 994 { 995 rtx set = single_set (prev); 996 997 if (set && rtx_equal_p (SET_DEST (set), reg)) 998 { 999 rtx src = SET_SRC (set); 1000 if (!REG_P (src) || HARD_REGISTER_P (src) 1001 || !pseudo_regno_single_word_and_live_p (REGNO (src))) 1002 break; 1003 if (!modified_between_p (src, prev, insn)) 1004 cheap_reg = src; 1005 break; 1006 } 1007 if (set && rtx_equal_p (SET_SRC (set), reg)) 1008 { 1009 rtx dest = SET_DEST (set); 1010 if (!REG_P (dest) || HARD_REGISTER_P (dest) 1011 || !pseudo_regno_single_word_and_live_p (REGNO (dest))) 1012 break; 1013 if (!modified_between_p (dest, prev, insn)) 1014 cheap_reg = dest; 1015 break; 1016 } 1017 1018 if (reg_set_p (reg, prev)) 1019 break; 1020 } 1021 prev = PREV_INSN (prev); 1022 } 1023 } 1024 return cheap_reg; 1025 } 1026 1027 /* Process insns of the basic block given by its LOOP_TREE_NODE to 1028 update allocno live ranges, allocno hard register conflicts, 1029 intersected calls, and register pressure info for allocnos for the 1030 basic block for and regions containing the basic block. */ 1031 static void 1032 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node) 1033 { 1034 int i, freq; 1035 unsigned int j; 1036 basic_block bb; 1037 rtx_insn *insn; 1038 bitmap_iterator bi; 1039 bitmap reg_live_out; 1040 unsigned int px; 1041 bool set_p; 1042 1043 bb = loop_tree_node->bb; 1044 if (bb != NULL) 1045 { 1046 for (i = 0; i < ira_pressure_classes_num; i++) 1047 { 1048 curr_reg_pressure[ira_pressure_classes[i]] = 0; 1049 high_pressure_start_point[ira_pressure_classes[i]] = -1; 1050 } 1051 curr_bb_node = loop_tree_node; 1052 reg_live_out = df_get_live_out (bb); 1053 sparseset_clear (objects_live); 1054 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out); 1055 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset); 1056 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs); 1057 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1058 if (TEST_HARD_REG_BIT (hard_regs_live, i)) 1059 { 1060 enum reg_class aclass, pclass, cl; 1061 1062 aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)]; 1063 pclass = ira_pressure_class_translate[aclass]; 1064 for (j = 0; 1065 (cl = ira_reg_class_super_classes[pclass][j]) 1066 != LIM_REG_CLASSES; 1067 j++) 1068 { 1069 if (! ira_reg_pressure_class_p[cl]) 1070 continue; 1071 curr_reg_pressure[cl]++; 1072 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl]) 1073 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl]; 1074 ira_assert (curr_reg_pressure[cl] 1075 <= ira_class_hard_regs_num[cl]); 1076 } 1077 } 1078 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi) 1079 mark_pseudo_regno_live (j); 1080 1081 freq = REG_FREQ_FROM_BB (bb); 1082 if (freq == 0) 1083 freq = 1; 1084 1085 /* Invalidate all allocno_saved_at_call entries. */ 1086 last_call_num++; 1087 1088 /* Scan the code of this basic block, noting which allocnos and 1089 hard regs are born or die. 1090 1091 Note that this loop treats uninitialized values as live until 1092 the beginning of the block. For example, if an instruction 1093 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever 1094 set, FOO will remain live until the beginning of the block. 1095 Likewise if FOO is not set at all. This is unnecessarily 1096 pessimistic, but it probably doesn't matter much in practice. */ 1097 FOR_BB_INSNS_REVERSE (bb, insn) 1098 { 1099 ira_allocno_t a; 1100 df_ref def, use; 1101 bool call_p; 1102 1103 if (!NONDEBUG_INSN_P (insn)) 1104 continue; 1105 1106 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1107 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n", 1108 INSN_UID (insn), loop_tree_node->parent->loop_num, 1109 curr_point); 1110 1111 call_p = CALL_P (insn); 1112 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM 1113 int regno; 1114 bool clear_pic_use_conflict_p = false; 1115 /* Processing insn usage in call insn can create conflict 1116 with pic pseudo and pic hard reg and that is wrong. 1117 Check this situation and fix it at the end of the insn 1118 processing. */ 1119 if (call_p && pic_offset_table_rtx != NULL_RTX 1120 && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER 1121 && (a = ira_curr_regno_allocno_map[regno]) != NULL) 1122 clear_pic_use_conflict_p 1123 = (find_regno_fusage (insn, USE, REAL_PIC_OFFSET_TABLE_REGNUM) 1124 && ! TEST_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS 1125 (ALLOCNO_OBJECT (a, 0)), 1126 REAL_PIC_OFFSET_TABLE_REGNUM)); 1127 #endif 1128 1129 /* Mark each defined value as live. We need to do this for 1130 unused values because they still conflict with quantities 1131 that are live at the time of the definition. 1132 1133 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such 1134 references represent the effect of the called function 1135 on a call-clobbered register. Marking the register as 1136 live would stop us from allocating it to a call-crossing 1137 allocno. */ 1138 FOR_EACH_INSN_DEF (def, insn) 1139 if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) 1140 mark_ref_live (def); 1141 1142 /* If INSN has multiple outputs, then any value used in one 1143 of the outputs conflicts with the other outputs. Model this 1144 by making the used value live during the output phase. 1145 1146 It is unsafe to use !single_set here since it will ignore 1147 an unused output. Just because an output is unused does 1148 not mean the compiler can assume the side effect will not 1149 occur. Consider if ALLOCNO appears in the address of an 1150 output and we reload the output. If we allocate ALLOCNO 1151 to the same hard register as an unused output we could 1152 set the hard register before the output reload insn. */ 1153 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn)) 1154 FOR_EACH_INSN_USE (use, insn) 1155 { 1156 int i; 1157 rtx reg; 1158 1159 reg = DF_REF_REG (use); 1160 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 1161 { 1162 rtx set; 1163 1164 set = XVECEXP (PATTERN (insn), 0, i); 1165 if (GET_CODE (set) == SET 1166 && reg_overlap_mentioned_p (reg, SET_DEST (set))) 1167 { 1168 /* After the previous loop, this is a no-op if 1169 REG is contained within SET_DEST (SET). */ 1170 mark_ref_live (use); 1171 break; 1172 } 1173 } 1174 } 1175 1176 extract_insn (insn); 1177 preferred_alternatives = get_preferred_alternatives (insn); 1178 preprocess_constraints (insn); 1179 process_single_reg_class_operands (false, freq); 1180 1181 /* See which defined values die here. */ 1182 FOR_EACH_INSN_DEF (def, insn) 1183 if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) 1184 mark_ref_dead (def); 1185 1186 if (call_p) 1187 { 1188 /* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from 1189 there, try to find a pseudo that is live across the call but 1190 can be cheaply reconstructed from the return value. */ 1191 rtx cheap_reg = find_call_crossed_cheap_reg (insn); 1192 if (cheap_reg != NULL_RTX) 1193 add_reg_note (insn, REG_RETURNED, cheap_reg); 1194 1195 last_call_num++; 1196 sparseset_clear (allocnos_processed); 1197 /* The current set of live allocnos are live across the call. */ 1198 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i) 1199 { 1200 ira_object_t obj = ira_object_id_map[i]; 1201 a = OBJECT_ALLOCNO (obj); 1202 int num = ALLOCNO_NUM (a); 1203 HARD_REG_SET this_call_used_reg_set; 1204 1205 get_call_reg_set_usage (insn, &this_call_used_reg_set, 1206 call_used_reg_set); 1207 1208 /* Don't allocate allocnos that cross setjmps or any 1209 call, if this function receives a nonlocal 1210 goto. */ 1211 if (cfun->has_nonlocal_label 1212 || find_reg_note (insn, REG_SETJMP, 1213 NULL_RTX) != NULL_RTX) 1214 { 1215 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj)); 1216 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); 1217 } 1218 if (can_throw_internal (insn)) 1219 { 1220 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 1221 this_call_used_reg_set); 1222 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 1223 this_call_used_reg_set); 1224 } 1225 1226 if (sparseset_bit_p (allocnos_processed, num)) 1227 continue; 1228 sparseset_set_bit (allocnos_processed, num); 1229 1230 if (allocno_saved_at_call[num] != last_call_num) 1231 /* Here we are mimicking caller-save.c behavior 1232 which does not save hard register at a call if 1233 it was saved on previous call in the same basic 1234 block and the hard register was not mentioned 1235 between the two calls. */ 1236 ALLOCNO_CALL_FREQ (a) += freq; 1237 /* Mark it as saved at the next call. */ 1238 allocno_saved_at_call[num] = last_call_num + 1; 1239 ALLOCNO_CALLS_CROSSED_NUM (a)++; 1240 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a), 1241 this_call_used_reg_set); 1242 if (cheap_reg != NULL_RTX 1243 && ALLOCNO_REGNO (a) == (int) REGNO (cheap_reg)) 1244 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)++; 1245 } 1246 } 1247 1248 make_early_clobber_and_input_conflicts (); 1249 1250 curr_point++; 1251 1252 /* Mark each used value as live. */ 1253 FOR_EACH_INSN_USE (use, insn) 1254 mark_ref_live (use); 1255 1256 process_single_reg_class_operands (true, freq); 1257 1258 set_p = mark_hard_reg_early_clobbers (insn, true); 1259 1260 if (set_p) 1261 { 1262 mark_hard_reg_early_clobbers (insn, false); 1263 1264 /* Mark each hard reg as live again. For example, a 1265 hard register can be in clobber and in an insn 1266 input. */ 1267 FOR_EACH_INSN_USE (use, insn) 1268 { 1269 rtx ureg = DF_REF_REG (use); 1270 1271 if (GET_CODE (ureg) == SUBREG) 1272 ureg = SUBREG_REG (ureg); 1273 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER) 1274 continue; 1275 1276 mark_ref_live (use); 1277 } 1278 } 1279 1280 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM 1281 if (clear_pic_use_conflict_p) 1282 { 1283 regno = REGNO (pic_offset_table_rtx); 1284 a = ira_curr_regno_allocno_map[regno]; 1285 CLEAR_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (ALLOCNO_OBJECT (a, 0)), 1286 REAL_PIC_OFFSET_TABLE_REGNUM); 1287 CLEAR_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS 1288 (ALLOCNO_OBJECT (a, 0)), 1289 REAL_PIC_OFFSET_TABLE_REGNUM); 1290 } 1291 #endif 1292 curr_point++; 1293 } 1294 1295 if (bb_has_eh_pred (bb)) 1296 for (j = 0; ; ++j) 1297 { 1298 unsigned int regno = EH_RETURN_DATA_REGNO (j); 1299 if (regno == INVALID_REGNUM) 1300 break; 1301 make_hard_regno_born (regno); 1302 } 1303 1304 /* Allocnos can't go in stack regs at the start of a basic block 1305 that is reached by an abnormal edge. Likewise for call 1306 clobbered regs, because caller-save, fixup_abnormal_edges and 1307 possibly the table driven EH machinery are not quite ready to 1308 handle such allocnos live across such edges. */ 1309 if (bb_has_abnormal_pred (bb)) 1310 { 1311 #ifdef STACK_REGS 1312 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px) 1313 { 1314 ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]); 1315 1316 ALLOCNO_NO_STACK_REG_P (a) = true; 1317 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true; 1318 } 1319 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++) 1320 make_hard_regno_born (px); 1321 #endif 1322 /* No need to record conflicts for call clobbered regs if we 1323 have nonlocal labels around, as we don't ever try to 1324 allocate such regs in this case. */ 1325 if (!cfun->has_nonlocal_label 1326 && has_abnormal_call_or_eh_pred_edge_p (bb)) 1327 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++) 1328 if (call_used_regs[px] 1329 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM 1330 /* We should create a conflict of PIC pseudo with 1331 PIC hard reg as PIC hard reg can have a wrong 1332 value after jump described by the abnormal edge. 1333 In this case we can not allocate PIC hard reg to 1334 PIC pseudo as PIC pseudo will also have a wrong 1335 value. This code is not critical as LRA can fix 1336 it but it is better to have the right allocation 1337 earlier. */ 1338 || (px == REAL_PIC_OFFSET_TABLE_REGNUM 1339 && pic_offset_table_rtx != NULL_RTX 1340 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER) 1341 #endif 1342 ) 1343 make_hard_regno_born (px); 1344 } 1345 1346 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i) 1347 make_object_dead (ira_object_id_map[i]); 1348 1349 curr_point++; 1350 1351 } 1352 /* Propagate register pressure to upper loop tree nodes. */ 1353 if (loop_tree_node != ira_loop_tree_root) 1354 for (i = 0; i < ira_pressure_classes_num; i++) 1355 { 1356 enum reg_class pclass; 1357 1358 pclass = ira_pressure_classes[i]; 1359 if (loop_tree_node->reg_pressure[pclass] 1360 > loop_tree_node->parent->reg_pressure[pclass]) 1361 loop_tree_node->parent->reg_pressure[pclass] 1362 = loop_tree_node->reg_pressure[pclass]; 1363 } 1364 } 1365 1366 /* Create and set up IRA_START_POINT_RANGES and 1367 IRA_FINISH_POINT_RANGES. */ 1368 static void 1369 create_start_finish_chains (void) 1370 { 1371 ira_object_t obj; 1372 ira_object_iterator oi; 1373 live_range_t r; 1374 1375 ira_start_point_ranges 1376 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t)); 1377 memset (ira_start_point_ranges, 0, ira_max_point * sizeof (live_range_t)); 1378 ira_finish_point_ranges 1379 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t)); 1380 memset (ira_finish_point_ranges, 0, ira_max_point * sizeof (live_range_t)); 1381 FOR_EACH_OBJECT (obj, oi) 1382 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 1383 { 1384 r->start_next = ira_start_point_ranges[r->start]; 1385 ira_start_point_ranges[r->start] = r; 1386 r->finish_next = ira_finish_point_ranges[r->finish]; 1387 ira_finish_point_ranges[r->finish] = r; 1388 } 1389 } 1390 1391 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after 1392 new live ranges and program points were added as a result if new 1393 insn generation. */ 1394 void 1395 ira_rebuild_start_finish_chains (void) 1396 { 1397 ira_free (ira_finish_point_ranges); 1398 ira_free (ira_start_point_ranges); 1399 create_start_finish_chains (); 1400 } 1401 1402 /* Compress allocno live ranges by removing program points where 1403 nothing happens. */ 1404 static void 1405 remove_some_program_points_and_update_live_ranges (void) 1406 { 1407 unsigned i; 1408 int n; 1409 int *map; 1410 ira_object_t obj; 1411 ira_object_iterator oi; 1412 live_range_t r, prev_r, next_r; 1413 sbitmap_iterator sbi; 1414 bool born_p, dead_p, prev_born_p, prev_dead_p; 1415 1416 auto_sbitmap born (ira_max_point); 1417 auto_sbitmap dead (ira_max_point); 1418 bitmap_clear (born); 1419 bitmap_clear (dead); 1420 FOR_EACH_OBJECT (obj, oi) 1421 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 1422 { 1423 ira_assert (r->start <= r->finish); 1424 bitmap_set_bit (born, r->start); 1425 bitmap_set_bit (dead, r->finish); 1426 } 1427 1428 auto_sbitmap born_or_dead (ira_max_point); 1429 bitmap_ior (born_or_dead, born, dead); 1430 map = (int *) ira_allocate (sizeof (int) * ira_max_point); 1431 n = -1; 1432 prev_born_p = prev_dead_p = false; 1433 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi) 1434 { 1435 born_p = bitmap_bit_p (born, i); 1436 dead_p = bitmap_bit_p (dead, i); 1437 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p) 1438 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p)) 1439 map[i] = n; 1440 else 1441 map[i] = ++n; 1442 prev_born_p = born_p; 1443 prev_dead_p = dead_p; 1444 } 1445 1446 n++; 1447 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 1448 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n", 1449 ira_max_point, n, 100 * n / ira_max_point); 1450 ira_max_point = n; 1451 1452 FOR_EACH_OBJECT (obj, oi) 1453 for (r = OBJECT_LIVE_RANGES (obj), prev_r = NULL; r != NULL; r = next_r) 1454 { 1455 next_r = r->next; 1456 r->start = map[r->start]; 1457 r->finish = map[r->finish]; 1458 if (prev_r == NULL || prev_r->start > r->finish + 1) 1459 { 1460 prev_r = r; 1461 continue; 1462 } 1463 prev_r->start = r->start; 1464 prev_r->next = next_r; 1465 ira_finish_live_range (r); 1466 } 1467 1468 ira_free (map); 1469 } 1470 1471 /* Print live ranges R to file F. */ 1472 void 1473 ira_print_live_range_list (FILE *f, live_range_t r) 1474 { 1475 for (; r != NULL; r = r->next) 1476 fprintf (f, " [%d..%d]", r->start, r->finish); 1477 fprintf (f, "\n"); 1478 } 1479 1480 DEBUG_FUNCTION void 1481 debug (live_range &ref) 1482 { 1483 ira_print_live_range_list (stderr, &ref); 1484 } 1485 1486 DEBUG_FUNCTION void 1487 debug (live_range *ptr) 1488 { 1489 if (ptr) 1490 debug (*ptr); 1491 else 1492 fprintf (stderr, "<nil>\n"); 1493 } 1494 1495 /* Print live ranges R to stderr. */ 1496 void 1497 ira_debug_live_range_list (live_range_t r) 1498 { 1499 ira_print_live_range_list (stderr, r); 1500 } 1501 1502 /* Print live ranges of object OBJ to file F. */ 1503 static void 1504 print_object_live_ranges (FILE *f, ira_object_t obj) 1505 { 1506 ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj)); 1507 } 1508 1509 /* Print live ranges of allocno A to file F. */ 1510 static void 1511 print_allocno_live_ranges (FILE *f, ira_allocno_t a) 1512 { 1513 int n = ALLOCNO_NUM_OBJECTS (a); 1514 int i; 1515 1516 for (i = 0; i < n; i++) 1517 { 1518 fprintf (f, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 1519 if (n > 1) 1520 fprintf (f, " [%d]", i); 1521 fprintf (f, "):"); 1522 print_object_live_ranges (f, ALLOCNO_OBJECT (a, i)); 1523 } 1524 } 1525 1526 /* Print live ranges of allocno A to stderr. */ 1527 void 1528 ira_debug_allocno_live_ranges (ira_allocno_t a) 1529 { 1530 print_allocno_live_ranges (stderr, a); 1531 } 1532 1533 /* Print live ranges of all allocnos to file F. */ 1534 static void 1535 print_live_ranges (FILE *f) 1536 { 1537 ira_allocno_t a; 1538 ira_allocno_iterator ai; 1539 1540 FOR_EACH_ALLOCNO (a, ai) 1541 print_allocno_live_ranges (f, a); 1542 } 1543 1544 /* Print live ranges of all allocnos to stderr. */ 1545 void 1546 ira_debug_live_ranges (void) 1547 { 1548 print_live_ranges (stderr); 1549 } 1550 1551 /* The main entry function creates live ranges, set up 1552 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and 1553 calculate register pressure info. */ 1554 void 1555 ira_create_allocno_live_ranges (void) 1556 { 1557 objects_live = sparseset_alloc (ira_objects_num); 1558 allocnos_processed = sparseset_alloc (ira_allocnos_num); 1559 curr_point = 0; 1560 last_call_num = 0; 1561 allocno_saved_at_call 1562 = (int *) ira_allocate (ira_allocnos_num * sizeof (int)); 1563 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int)); 1564 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, 1565 process_bb_node_lives); 1566 ira_max_point = curr_point; 1567 create_start_finish_chains (); 1568 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1569 print_live_ranges (ira_dump_file); 1570 /* Clean up. */ 1571 ira_free (allocno_saved_at_call); 1572 sparseset_free (objects_live); 1573 sparseset_free (allocnos_processed); 1574 } 1575 1576 /* Compress allocno live ranges. */ 1577 void 1578 ira_compress_allocno_live_ranges (void) 1579 { 1580 remove_some_program_points_and_update_live_ranges (); 1581 ira_rebuild_start_finish_chains (); 1582 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 1583 { 1584 fprintf (ira_dump_file, "Ranges after the compression:\n"); 1585 print_live_ranges (ira_dump_file); 1586 } 1587 } 1588 1589 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */ 1590 void 1591 ira_finish_allocno_live_ranges (void) 1592 { 1593 ira_free (ira_finish_point_ranges); 1594 ira_free (ira_start_point_ranges); 1595 } 1596