1 /* Build live ranges for 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 contains code to build pseudo live-ranges (analogous 23 structures used in IRA, so read comments about the live-ranges 24 there) and other info necessary for other passes to assign 25 hard-registers to pseudos, coalesce the spilled pseudos, and assign 26 stack memory slots to spilled pseudos. */ 27 28 #include "config.h" 29 #include "system.h" 30 #include "coretypes.h" 31 #include "backend.h" 32 #include "rtl.h" 33 #include "tree.h" 34 #include "predict.h" 35 #include "df.h" 36 #include "memmodel.h" 37 #include "tm_p.h" 38 #include "insn-config.h" 39 #include "regs.h" 40 #include "ira.h" 41 #include "recog.h" 42 #include "cfganal.h" 43 #include "sparseset.h" 44 #include "lra-int.h" 45 #include "target.h" 46 47 /* Program points are enumerated by numbers from range 48 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more 49 program points than insns. Program points are places in the 50 program where liveness info can be changed. In most general case 51 (there are more complicated cases too) some program points 52 correspond to places where input operand dies and other ones 53 correspond to places where output operands are born. */ 54 int lra_live_max_point; 55 56 /* Accumulated execution frequency of all references for each hard 57 register. */ 58 int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER]; 59 60 /* A global flag whose true value says to build live ranges for all 61 pseudos, otherwise the live ranges only for pseudos got memory is 62 build. True value means also building copies and setting up hard 63 register preferences. The complete info is necessary only for the 64 assignment pass. The complete info is not needed for the 65 coalescing and spill passes. */ 66 static bool complete_info_p; 67 68 /* Pseudos live at current point in the RTL scan. */ 69 static sparseset pseudos_live; 70 71 /* Pseudos probably living through calls and setjumps. As setjump is 72 a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up 73 then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up 74 too. These data are necessary for cases when only one subreg of a 75 multi-reg pseudo is set up after a call. So we decide it is 76 probably live when traversing bb backward. We are sure about 77 living when we see its usage or definition of the pseudo. */ 78 static sparseset pseudos_live_through_calls; 79 static sparseset pseudos_live_through_setjumps; 80 81 /* Set of hard regs (except eliminable ones) currently live. */ 82 static HARD_REG_SET hard_regs_live; 83 84 /* Set of pseudos and hard registers start living/dying in the current 85 insn. These sets are used to update REG_DEAD and REG_UNUSED notes 86 in the insn. */ 87 static sparseset start_living, start_dying; 88 89 /* Set of pseudos and hard regs dead and unused in the current 90 insn. */ 91 static sparseset unused_set, dead_set; 92 93 /* Bitmap used for holding intermediate bitmap operation results. */ 94 static bitmap_head temp_bitmap; 95 96 /* Pool for pseudo live ranges. */ 97 static object_allocator<lra_live_range> lra_live_range_pool ("live ranges"); 98 99 /* Free live range list LR. */ 100 static void 101 free_live_range_list (lra_live_range_t lr) 102 { 103 lra_live_range_t next; 104 105 while (lr != NULL) 106 { 107 next = lr->next; 108 lra_live_range_pool.remove (lr); 109 lr = next; 110 } 111 } 112 113 /* Create and return pseudo live range with given attributes. */ 114 static lra_live_range_t 115 create_live_range (int regno, int start, int finish, lra_live_range_t next) 116 { 117 lra_live_range_t p = lra_live_range_pool.allocate (); 118 p->regno = regno; 119 p->start = start; 120 p->finish = finish; 121 p->next = next; 122 return p; 123 } 124 125 /* Copy live range R and return the result. */ 126 static lra_live_range_t 127 copy_live_range (lra_live_range_t r) 128 { 129 return new (lra_live_range_pool) lra_live_range (*r); 130 } 131 132 /* Copy live range list given by its head R and return the result. */ 133 lra_live_range_t 134 lra_copy_live_range_list (lra_live_range_t r) 135 { 136 lra_live_range_t p, first, *chain; 137 138 first = NULL; 139 for (chain = &first; r != NULL; r = r->next) 140 { 141 p = copy_live_range (r); 142 *chain = p; 143 chain = &p->next; 144 } 145 return first; 146 } 147 148 /* Merge *non-intersected* ranges R1 and R2 and returns the result. 149 The function maintains the order of ranges and tries to minimize 150 size of the result range list. Ranges R1 and R2 may not be used 151 after the call. */ 152 lra_live_range_t 153 lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2) 154 { 155 lra_live_range_t first, last; 156 157 if (r1 == NULL) 158 return r2; 159 if (r2 == NULL) 160 return r1; 161 for (first = last = NULL; r1 != NULL && r2 != NULL;) 162 { 163 if (r1->start < r2->start) 164 std::swap (r1, r2); 165 166 if (r1->start == r2->finish + 1) 167 { 168 /* Joint ranges: merge r1 and r2 into r1. */ 169 r1->start = r2->start; 170 lra_live_range_t temp = r2; 171 r2 = r2->next; 172 lra_live_range_pool.remove (temp); 173 } 174 else 175 { 176 gcc_assert (r2->finish + 1 < r1->start); 177 /* Add r1 to the result. */ 178 if (first == NULL) 179 first = last = r1; 180 else 181 { 182 last->next = r1; 183 last = r1; 184 } 185 r1 = r1->next; 186 } 187 } 188 if (r1 != NULL) 189 { 190 if (first == NULL) 191 first = r1; 192 else 193 last->next = r1; 194 } 195 else 196 { 197 lra_assert (r2 != NULL); 198 if (first == NULL) 199 first = r2; 200 else 201 last->next = r2; 202 } 203 return first; 204 } 205 206 /* Return TRUE if live ranges R1 and R2 intersect. */ 207 bool 208 lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2) 209 { 210 /* Remember the live ranges are always kept ordered. */ 211 while (r1 != NULL && r2 != NULL) 212 { 213 if (r1->start > r2->finish) 214 r1 = r1->next; 215 else if (r2->start > r1->finish) 216 r2 = r2->next; 217 else 218 return true; 219 } 220 return false; 221 } 222 223 /* The corresponding bitmaps of BB currently being processed. */ 224 static bitmap bb_killed_pseudos, bb_gen_pseudos; 225 226 /* The function processing birth of hard register REGNO. It updates 227 living hard regs, START_LIVING, and conflict hard regs for living 228 pseudos. Conflict hard regs for the pic pseudo is not updated if 229 REGNO is REAL_PIC_OFFSET_TABLE_REGNUM and CHECK_PIC_PSEUDO_P is 230 true. */ 231 static void 232 make_hard_regno_born (int regno, bool check_pic_pseudo_p ATTRIBUTE_UNUSED) 233 { 234 unsigned int i; 235 236 lra_assert (regno < FIRST_PSEUDO_REGISTER); 237 if (TEST_HARD_REG_BIT (hard_regs_live, regno)) 238 return; 239 SET_HARD_REG_BIT (hard_regs_live, regno); 240 sparseset_set_bit (start_living, regno); 241 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i) 242 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM 243 if (! check_pic_pseudo_p 244 || regno != REAL_PIC_OFFSET_TABLE_REGNUM 245 || pic_offset_table_rtx == NULL 246 || i != REGNO (pic_offset_table_rtx)) 247 #endif 248 SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno); 249 if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno)) 250 bitmap_set_bit (bb_gen_pseudos, regno); 251 } 252 253 /* Process the death of hard register REGNO. This updates 254 hard_regs_live and START_DYING. */ 255 static void 256 make_hard_regno_dead (int regno) 257 { 258 lra_assert (regno < FIRST_PSEUDO_REGISTER); 259 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)) 260 return; 261 sparseset_set_bit (start_dying, regno); 262 CLEAR_HARD_REG_BIT (hard_regs_live, regno); 263 if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno)) 264 { 265 bitmap_clear_bit (bb_gen_pseudos, regno); 266 bitmap_set_bit (bb_killed_pseudos, regno); 267 } 268 } 269 270 /* Mark pseudo REGNO as living at program point POINT, update conflicting 271 hard registers of the pseudo and START_LIVING, and start a new live 272 range for the pseudo corresponding to REGNO if it is necessary. */ 273 static void 274 mark_pseudo_live (int regno, int point) 275 { 276 lra_live_range_t p; 277 278 lra_assert (regno >= FIRST_PSEUDO_REGISTER); 279 lra_assert (! sparseset_bit_p (pseudos_live, regno)); 280 sparseset_set_bit (pseudos_live, regno); 281 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, hard_regs_live); 282 283 if ((complete_info_p || lra_get_regno_hard_regno (regno) < 0) 284 && ((p = lra_reg_info[regno].live_ranges) == NULL 285 || (p->finish != point && p->finish + 1 != point))) 286 lra_reg_info[regno].live_ranges 287 = create_live_range (regno, point, -1, p); 288 sparseset_set_bit (start_living, regno); 289 } 290 291 /* Mark pseudo REGNO as not living at program point POINT and update 292 START_DYING. 293 This finishes the current live range for the pseudo corresponding 294 to REGNO. */ 295 static void 296 mark_pseudo_dead (int regno, int point) 297 { 298 lra_live_range_t p; 299 300 lra_assert (regno >= FIRST_PSEUDO_REGISTER); 301 lra_assert (sparseset_bit_p (pseudos_live, regno)); 302 sparseset_clear_bit (pseudos_live, regno); 303 sparseset_set_bit (start_dying, regno); 304 if (complete_info_p || lra_get_regno_hard_regno (regno) < 0) 305 { 306 p = lra_reg_info[regno].live_ranges; 307 lra_assert (p != NULL); 308 p->finish = point; 309 } 310 } 311 312 /* Mark register REGNO (pseudo or hard register) in MODE as live at 313 program point POINT. Update BB_GEN_PSEUDOS. 314 Return TRUE if the liveness tracking sets were modified, or FALSE 315 if nothing changed. */ 316 static bool 317 mark_regno_live (int regno, machine_mode mode, int point) 318 { 319 int last; 320 bool changed = false; 321 322 if (regno < FIRST_PSEUDO_REGISTER) 323 { 324 for (last = end_hard_regno (mode, regno); regno < last; regno++) 325 make_hard_regno_born (regno, false); 326 } 327 else 328 { 329 if (! sparseset_bit_p (pseudos_live, regno)) 330 { 331 mark_pseudo_live (regno, point); 332 changed = true; 333 } 334 bitmap_set_bit (bb_gen_pseudos, regno); 335 } 336 return changed; 337 } 338 339 340 /* Mark register REGNO in MODE as dead at program point POINT. Update 341 BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. Return TRUE if the liveness 342 tracking sets were modified, or FALSE if nothing changed. */ 343 static bool 344 mark_regno_dead (int regno, machine_mode mode, int point) 345 { 346 int last; 347 bool changed = false; 348 349 if (regno < FIRST_PSEUDO_REGISTER) 350 { 351 for (last = end_hard_regno (mode, regno); regno < last; regno++) 352 make_hard_regno_dead (regno); 353 } 354 else 355 { 356 if (sparseset_bit_p (pseudos_live, regno)) 357 { 358 mark_pseudo_dead (regno, point); 359 changed = true; 360 } 361 bitmap_clear_bit (bb_gen_pseudos, regno); 362 bitmap_set_bit (bb_killed_pseudos, regno); 363 } 364 return changed; 365 } 366 367 368 369 /* This page contains code for making global live analysis of pseudos. 370 The code works only when pseudo live info is changed on a BB 371 border. That might be a consequence of some global transformations 372 in LRA, e.g. PIC pseudo reuse or rematerialization. */ 373 374 /* Structure describing local BB data used for pseudo 375 live-analysis. */ 376 struct bb_data_pseudos 377 { 378 /* Basic block about which the below data are. */ 379 basic_block bb; 380 bitmap_head killed_pseudos; /* pseudos killed in the BB. */ 381 bitmap_head gen_pseudos; /* pseudos generated in the BB. */ 382 }; 383 384 /* Array for all BB data. Indexed by the corresponding BB index. */ 385 typedef struct bb_data_pseudos *bb_data_t; 386 387 /* All basic block data are referred through the following array. */ 388 static bb_data_t bb_data; 389 390 /* Two small functions for access to the bb data. */ 391 static inline bb_data_t 392 get_bb_data (basic_block bb) 393 { 394 return &bb_data[(bb)->index]; 395 } 396 397 static inline bb_data_t 398 get_bb_data_by_index (int index) 399 { 400 return &bb_data[index]; 401 } 402 403 /* Bitmap with all hard regs. */ 404 static bitmap_head all_hard_regs_bitmap; 405 406 /* The transfer function used by the DF equation solver to propagate 407 live info through block with BB_INDEX according to the following 408 equation: 409 410 bb.livein = (bb.liveout - bb.kill) OR bb.gen 411 */ 412 static bool 413 live_trans_fun (int bb_index) 414 { 415 basic_block bb = get_bb_data_by_index (bb_index)->bb; 416 bitmap bb_liveout = df_get_live_out (bb); 417 bitmap bb_livein = df_get_live_in (bb); 418 bb_data_t bb_info = get_bb_data (bb); 419 420 bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap); 421 return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos, 422 &temp_bitmap, &bb_info->killed_pseudos); 423 } 424 425 /* The confluence function used by the DF equation solver to set up 426 live info for a block BB without predecessor. */ 427 static void 428 live_con_fun_0 (basic_block bb) 429 { 430 bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap); 431 } 432 433 /* The confluence function used by the DF equation solver to propagate 434 live info from successor to predecessor on edge E according to the 435 following equation: 436 437 bb.liveout = 0 for entry block | OR (livein of successors) 438 */ 439 static bool 440 live_con_fun_n (edge e) 441 { 442 basic_block bb = e->src; 443 basic_block dest = e->dest; 444 bitmap bb_liveout = df_get_live_out (bb); 445 bitmap dest_livein = df_get_live_in (dest); 446 447 return bitmap_ior_and_compl_into (bb_liveout, 448 dest_livein, &all_hard_regs_bitmap); 449 } 450 451 /* Indexes of all function blocks. */ 452 static bitmap_head all_blocks; 453 454 /* Allocate and initialize data needed for global pseudo live 455 analysis. */ 456 static void 457 initiate_live_solver (void) 458 { 459 bitmap_initialize (&all_hard_regs_bitmap, ®_obstack); 460 bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER); 461 bb_data = XNEWVEC (struct bb_data_pseudos, last_basic_block_for_fn (cfun)); 462 bitmap_initialize (&all_blocks, ®_obstack); 463 464 basic_block bb; 465 FOR_ALL_BB_FN (bb, cfun) 466 { 467 bb_data_t bb_info = get_bb_data (bb); 468 bb_info->bb = bb; 469 bitmap_initialize (&bb_info->killed_pseudos, ®_obstack); 470 bitmap_initialize (&bb_info->gen_pseudos, ®_obstack); 471 bitmap_set_bit (&all_blocks, bb->index); 472 } 473 } 474 475 /* Free all data needed for global pseudo live analysis. */ 476 static void 477 finish_live_solver (void) 478 { 479 basic_block bb; 480 481 bitmap_clear (&all_blocks); 482 FOR_ALL_BB_FN (bb, cfun) 483 { 484 bb_data_t bb_info = get_bb_data (bb); 485 bitmap_clear (&bb_info->killed_pseudos); 486 bitmap_clear (&bb_info->gen_pseudos); 487 } 488 free (bb_data); 489 bitmap_clear (&all_hard_regs_bitmap); 490 } 491 492 493 494 /* Insn currently scanned. */ 495 static rtx_insn *curr_insn; 496 /* The insn data. */ 497 static lra_insn_recog_data_t curr_id; 498 /* The insn static data. */ 499 static struct lra_static_insn_data *curr_static_id; 500 501 /* Vec containing execution frequencies of program points. */ 502 static vec<int> point_freq_vec; 503 504 /* The start of the above vector elements. */ 505 int *lra_point_freq; 506 507 /* Increment the current program point POINT to the next point which has 508 execution frequency FREQ. */ 509 static void 510 next_program_point (int &point, int freq) 511 { 512 point_freq_vec.safe_push (freq); 513 lra_point_freq = point_freq_vec.address (); 514 point++; 515 } 516 517 /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */ 518 void 519 lra_setup_reload_pseudo_preferenced_hard_reg (int regno, 520 int hard_regno, int profit) 521 { 522 lra_assert (regno >= lra_constraint_new_regno_start); 523 if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno) 524 lra_reg_info[regno].preferred_hard_regno_profit1 += profit; 525 else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno) 526 lra_reg_info[regno].preferred_hard_regno_profit2 += profit; 527 else if (lra_reg_info[regno].preferred_hard_regno1 < 0) 528 { 529 lra_reg_info[regno].preferred_hard_regno1 = hard_regno; 530 lra_reg_info[regno].preferred_hard_regno_profit1 = profit; 531 } 532 else if (lra_reg_info[regno].preferred_hard_regno2 < 0 533 || profit > lra_reg_info[regno].preferred_hard_regno_profit2) 534 { 535 lra_reg_info[regno].preferred_hard_regno2 = hard_regno; 536 lra_reg_info[regno].preferred_hard_regno_profit2 = profit; 537 } 538 else 539 return; 540 /* Keep the 1st hard regno as more profitable. */ 541 if (lra_reg_info[regno].preferred_hard_regno1 >= 0 542 && lra_reg_info[regno].preferred_hard_regno2 >= 0 543 && (lra_reg_info[regno].preferred_hard_regno_profit2 544 > lra_reg_info[regno].preferred_hard_regno_profit1)) 545 { 546 std::swap (lra_reg_info[regno].preferred_hard_regno1, 547 lra_reg_info[regno].preferred_hard_regno2); 548 std::swap (lra_reg_info[regno].preferred_hard_regno_profit1, 549 lra_reg_info[regno].preferred_hard_regno_profit2); 550 } 551 if (lra_dump_file != NULL) 552 { 553 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0) 554 fprintf (lra_dump_file, 555 " Hard reg %d is preferable by r%d with profit %d\n", 556 hard_regno, regno, 557 lra_reg_info[regno].preferred_hard_regno_profit1); 558 if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0) 559 fprintf (lra_dump_file, 560 " Hard reg %d is preferable by r%d with profit %d\n", 561 hard_regno, regno, 562 lra_reg_info[regno].preferred_hard_regno_profit2); 563 } 564 } 565 566 /* Check that REGNO living through calls and setjumps, set up conflict 567 regs using LAST_CALL_USED_REG_SET, and clear corresponding bits in 568 PSEUDOS_LIVE_THROUGH_CALLS and PSEUDOS_LIVE_THROUGH_SETJUMPS. */ 569 static inline void 570 check_pseudos_live_through_calls (int regno, 571 HARD_REG_SET last_call_used_reg_set) 572 { 573 int hr; 574 575 if (! sparseset_bit_p (pseudos_live_through_calls, regno)) 576 return; 577 sparseset_clear_bit (pseudos_live_through_calls, regno); 578 IOR_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs, 579 last_call_used_reg_set); 580 581 for (hr = 0; hr < FIRST_PSEUDO_REGISTER; hr++) 582 if (targetm.hard_regno_call_part_clobbered (hr, 583 PSEUDO_REGNO_MODE (regno))) 584 SET_HARD_REG_BIT (lra_reg_info[regno].conflict_hard_regs, hr); 585 lra_reg_info[regno].call_p = true; 586 if (! sparseset_bit_p (pseudos_live_through_setjumps, regno)) 587 return; 588 sparseset_clear_bit (pseudos_live_through_setjumps, regno); 589 /* Don't allocate pseudos that cross setjmps or any call, if this 590 function receives a nonlocal goto. */ 591 SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs); 592 } 593 594 /* Return true if insn REG is an early clobber operand in alternative 595 NALT. Negative NALT means that we don't know the current insn 596 alternative. So assume the worst. */ 597 static inline bool 598 reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt) 599 { 600 return (reg->early_clobber 601 && (n_alt == LRA_UNKNOWN_ALT 602 || (n_alt != LRA_NON_CLOBBERED_ALT 603 && TEST_BIT (reg->early_clobber_alts, n_alt)))); 604 } 605 606 /* Process insns of the basic block BB to update pseudo live ranges, 607 pseudo hard register conflicts, and insn notes. We do it on 608 backward scan of BB insns. CURR_POINT is the program point where 609 BB ends. The function updates this counter and returns in 610 CURR_POINT the program point where BB starts. The function also 611 does local live info updates and can delete the dead insns if 612 DEAD_INSN_P. It returns true if pseudo live info was 613 changed at the BB start. */ 614 static bool 615 process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p) 616 { 617 int i, regno, freq; 618 unsigned int j; 619 bitmap_iterator bi; 620 bitmap reg_live_out; 621 unsigned int px; 622 rtx_insn *next; 623 rtx link, *link_loc; 624 bool need_curr_point_incr; 625 HARD_REG_SET last_call_used_reg_set; 626 627 reg_live_out = df_get_live_out (bb); 628 sparseset_clear (pseudos_live); 629 sparseset_clear (pseudos_live_through_calls); 630 sparseset_clear (pseudos_live_through_setjumps); 631 CLEAR_HARD_REG_SET (last_call_used_reg_set); 632 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out); 633 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset); 634 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi) 635 mark_pseudo_live (j, curr_point); 636 637 bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos; 638 bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos; 639 bitmap_clear (bb_gen_pseudos); 640 bitmap_clear (bb_killed_pseudos); 641 freq = REG_FREQ_FROM_BB (bb); 642 643 if (lra_dump_file != NULL) 644 fprintf (lra_dump_file, " BB %d\n", bb->index); 645 646 /* Scan the code of this basic block, noting which pseudos and hard 647 regs are born or die. 648 649 Note that this loop treats uninitialized values as live until the 650 beginning of the block. For example, if an instruction uses 651 (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set, 652 FOO will remain live until the beginning of the block. Likewise 653 if FOO is not set at all. This is unnecessarily pessimistic, but 654 it probably doesn't matter much in practice. */ 655 FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next) 656 { 657 bool call_p; 658 int n_alt, dst_regno, src_regno; 659 rtx set; 660 struct lra_insn_reg *reg; 661 662 if (!NONDEBUG_INSN_P (curr_insn)) 663 continue; 664 665 curr_id = lra_get_insn_recog_data (curr_insn); 666 curr_static_id = curr_id->insn_static_data; 667 n_alt = curr_id->used_insn_alternative; 668 if (lra_dump_file != NULL) 669 fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n", 670 INSN_UID (curr_insn), curr_point, n_alt); 671 672 set = single_set (curr_insn); 673 674 if (dead_insn_p && set != NULL_RTX 675 && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER 676 && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX 677 && ! may_trap_p (PATTERN (curr_insn)) 678 /* Don't do premature remove of pic offset pseudo as we can 679 start to use it after some reload generation. */ 680 && (pic_offset_table_rtx == NULL_RTX 681 || pic_offset_table_rtx != SET_DEST (set))) 682 { 683 bool remove_p = true; 684 685 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 686 if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno)) 687 { 688 remove_p = false; 689 break; 690 } 691 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next) 692 if (reg->type != OP_IN) 693 { 694 remove_p = false; 695 break; 696 } 697 if (remove_p && ! volatile_refs_p (PATTERN (curr_insn))) 698 { 699 dst_regno = REGNO (SET_DEST (set)); 700 if (lra_dump_file != NULL) 701 fprintf (lra_dump_file, " Deleting dead insn %u\n", 702 INSN_UID (curr_insn)); 703 lra_set_insn_deleted (curr_insn); 704 if (lra_reg_info[dst_regno].nrefs == 0) 705 { 706 /* There might be some debug insns with the pseudo. */ 707 unsigned int uid; 708 rtx_insn *insn; 709 710 bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap); 711 EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi) 712 { 713 insn = lra_insn_recog_data[uid]->insn; 714 lra_substitute_pseudo_within_insn (insn, dst_regno, 715 SET_SRC (set), true); 716 lra_update_insn_regno_info (insn); 717 } 718 } 719 continue; 720 } 721 } 722 723 /* Update max ref width and hard reg usage. */ 724 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 725 { 726 int i, regno = reg->regno; 727 728 if (partial_subreg_p (lra_reg_info[regno].biggest_mode, 729 reg->biggest_mode)) 730 lra_reg_info[regno].biggest_mode = reg->biggest_mode; 731 if (regno < FIRST_PSEUDO_REGISTER) 732 { 733 lra_hard_reg_usage[regno] += freq; 734 /* A hard register explicitly can be used in small mode, 735 but implicitly it can be used in natural mode as a 736 part of multi-register group. Process this case 737 here. */ 738 for (i = 1; i < hard_regno_nregs (regno, reg->biggest_mode); i++) 739 if (partial_subreg_p (lra_reg_info[regno + i].biggest_mode, 740 GET_MODE (regno_reg_rtx[regno + i]))) 741 lra_reg_info[regno + i].biggest_mode 742 = GET_MODE (regno_reg_rtx[regno + i]); 743 } 744 } 745 746 call_p = CALL_P (curr_insn); 747 src_regno = (set != NULL_RTX && REG_P (SET_SRC (set)) 748 ? REGNO (SET_SRC (set)) : -1); 749 dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set)) 750 ? REGNO (SET_DEST (set)) : -1); 751 if (complete_info_p 752 && src_regno >= 0 && dst_regno >= 0 753 /* Check that source regno does not conflict with 754 destination regno to exclude most impossible 755 preferences. */ 756 && (((src_regno >= FIRST_PSEUDO_REGISTER 757 && (! sparseset_bit_p (pseudos_live, src_regno) 758 || (dst_regno >= FIRST_PSEUDO_REGISTER 759 && lra_reg_val_equal_p (src_regno, 760 lra_reg_info[dst_regno].val, 761 lra_reg_info[dst_regno].offset)))) 762 || (src_regno < FIRST_PSEUDO_REGISTER 763 && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno))) 764 /* It might be 'inheritance pseudo <- reload pseudo'. */ 765 || (src_regno >= lra_constraint_new_regno_start 766 && dst_regno >= lra_constraint_new_regno_start 767 /* Remember to skip special cases where src/dest regnos are 768 the same, e.g. insn SET pattern has matching constraints 769 like =r,0. */ 770 && src_regno != dst_regno))) 771 { 772 int hard_regno = -1, regno = -1; 773 774 if (dst_regno >= lra_constraint_new_regno_start 775 && src_regno >= lra_constraint_new_regno_start) 776 { 777 /* It might be still an original (non-reload) insn with 778 one unused output and a constraint requiring to use 779 the same reg for input/output operands. In this case 780 dst_regno and src_regno have the same value, we don't 781 need a misleading copy for this case. */ 782 if (dst_regno != src_regno) 783 lra_create_copy (dst_regno, src_regno, freq); 784 } 785 else if (dst_regno >= lra_constraint_new_regno_start) 786 { 787 if ((hard_regno = src_regno) >= FIRST_PSEUDO_REGISTER) 788 hard_regno = reg_renumber[src_regno]; 789 regno = dst_regno; 790 } 791 else if (src_regno >= lra_constraint_new_regno_start) 792 { 793 if ((hard_regno = dst_regno) >= FIRST_PSEUDO_REGISTER) 794 hard_regno = reg_renumber[dst_regno]; 795 regno = src_regno; 796 } 797 if (regno >= 0 && hard_regno >= 0) 798 lra_setup_reload_pseudo_preferenced_hard_reg 799 (regno, hard_regno, freq); 800 } 801 802 sparseset_clear (start_living); 803 804 /* Try to avoid unnecessary program point increments, this saves 805 a lot of time in remove_some_program_points_and_update_live_ranges. 806 We only need an increment if something becomes live or dies at this 807 program point. */ 808 need_curr_point_incr = false; 809 810 /* Mark each defined value as live. We need to do this for 811 unused values because they still conflict with quantities 812 that are live at the time of the definition. */ 813 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 814 if (reg->type != OP_IN) 815 { 816 need_curr_point_incr 817 |= mark_regno_live (reg->regno, reg->biggest_mode, 818 curr_point); 819 check_pseudos_live_through_calls (reg->regno, 820 last_call_used_reg_set); 821 } 822 823 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next) 824 if (reg->type != OP_IN) 825 make_hard_regno_born (reg->regno, false); 826 827 if (curr_id->arg_hard_regs != NULL) 828 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++) 829 if (regno >= FIRST_PSEUDO_REGISTER) 830 /* It is a clobber. */ 831 make_hard_regno_born (regno - FIRST_PSEUDO_REGISTER, false); 832 833 sparseset_copy (unused_set, start_living); 834 835 sparseset_clear (start_dying); 836 837 /* See which defined values die here. */ 838 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 839 if (reg->type == OP_OUT 840 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p) 841 need_curr_point_incr 842 |= mark_regno_dead (reg->regno, reg->biggest_mode, 843 curr_point); 844 845 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next) 846 if (reg->type == OP_OUT 847 && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p) 848 make_hard_regno_dead (reg->regno); 849 850 if (curr_id->arg_hard_regs != NULL) 851 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++) 852 if (regno >= FIRST_PSEUDO_REGISTER) 853 /* It is a clobber. */ 854 make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER); 855 856 if (call_p) 857 { 858 if (! flag_ipa_ra) 859 COPY_HARD_REG_SET(last_call_used_reg_set, call_used_reg_set); 860 else 861 { 862 HARD_REG_SET this_call_used_reg_set; 863 get_call_reg_set_usage (curr_insn, &this_call_used_reg_set, 864 call_used_reg_set); 865 866 bool flush = (! hard_reg_set_empty_p (last_call_used_reg_set) 867 && ! hard_reg_set_equal_p (last_call_used_reg_set, 868 this_call_used_reg_set)); 869 870 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j) 871 { 872 IOR_HARD_REG_SET (lra_reg_info[j].actual_call_used_reg_set, 873 this_call_used_reg_set); 874 if (flush) 875 check_pseudos_live_through_calls 876 (j, last_call_used_reg_set); 877 } 878 COPY_HARD_REG_SET(last_call_used_reg_set, this_call_used_reg_set); 879 } 880 881 sparseset_ior (pseudos_live_through_calls, 882 pseudos_live_through_calls, pseudos_live); 883 if (cfun->has_nonlocal_label 884 || find_reg_note (curr_insn, REG_SETJMP, 885 NULL_RTX) != NULL_RTX) 886 sparseset_ior (pseudos_live_through_setjumps, 887 pseudos_live_through_setjumps, pseudos_live); 888 } 889 890 /* Increment the current program point if we must. */ 891 if (need_curr_point_incr) 892 next_program_point (curr_point, freq); 893 894 sparseset_clear (start_living); 895 896 need_curr_point_incr = false; 897 898 /* Mark each used value as live. */ 899 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 900 if (reg->type == OP_IN) 901 { 902 need_curr_point_incr 903 |= mark_regno_live (reg->regno, reg->biggest_mode, 904 curr_point); 905 check_pseudos_live_through_calls (reg->regno, 906 last_call_used_reg_set); 907 } 908 909 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next) 910 if (reg->type == OP_IN) 911 make_hard_regno_born (reg->regno, false); 912 913 if (curr_id->arg_hard_regs != NULL) 914 /* Make argument hard registers live. Don't create conflict 915 of used REAL_PIC_OFFSET_TABLE_REGNUM and the pic pseudo. */ 916 for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++) 917 if (regno < FIRST_PSEUDO_REGISTER) 918 make_hard_regno_born (regno, true); 919 920 sparseset_and_compl (dead_set, start_living, start_dying); 921 922 /* Mark early clobber outputs dead. */ 923 for (reg = curr_id->regs; reg != NULL; reg = reg->next) 924 if (reg->type == OP_OUT 925 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p) 926 need_curr_point_incr 927 |= mark_regno_dead (reg->regno, reg->biggest_mode, 928 curr_point); 929 930 for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next) 931 if (reg->type == OP_OUT 932 && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p) 933 { 934 struct lra_insn_reg *reg2; 935 936 /* We can have early clobbered non-operand hard reg and 937 the same hard reg as an insn input. Don't make hard 938 reg dead before the insns. */ 939 for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next) 940 if (reg2->type != OP_OUT && reg2->regno == reg->regno) 941 break; 942 if (reg2 == NULL) 943 make_hard_regno_dead (reg->regno); 944 } 945 946 if (need_curr_point_incr) 947 next_program_point (curr_point, freq); 948 949 /* Update notes. */ 950 for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;) 951 { 952 if (REG_NOTE_KIND (link) != REG_DEAD 953 && REG_NOTE_KIND (link) != REG_UNUSED) 954 ; 955 else if (REG_P (XEXP (link, 0))) 956 { 957 regno = REGNO (XEXP (link, 0)); 958 if ((REG_NOTE_KIND (link) == REG_DEAD 959 && ! sparseset_bit_p (dead_set, regno)) 960 || (REG_NOTE_KIND (link) == REG_UNUSED 961 && ! sparseset_bit_p (unused_set, regno))) 962 { 963 *link_loc = XEXP (link, 1); 964 continue; 965 } 966 if (REG_NOTE_KIND (link) == REG_DEAD) 967 sparseset_clear_bit (dead_set, regno); 968 else if (REG_NOTE_KIND (link) == REG_UNUSED) 969 sparseset_clear_bit (unused_set, regno); 970 } 971 link_loc = &XEXP (link, 1); 972 } 973 EXECUTE_IF_SET_IN_SPARSESET (dead_set, j) 974 add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]); 975 EXECUTE_IF_SET_IN_SPARSESET (unused_set, j) 976 add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]); 977 } 978 979 if (bb_has_eh_pred (bb)) 980 for (j = 0; ; ++j) 981 { 982 unsigned int regno = EH_RETURN_DATA_REGNO (j); 983 984 if (regno == INVALID_REGNUM) 985 break; 986 make_hard_regno_born (regno, false); 987 } 988 989 /* Pseudos can't go in stack regs at the start of a basic block that 990 is reached by an abnormal edge. Likewise for call clobbered regs, 991 because caller-save, fixup_abnormal_edges and possibly the table 992 driven EH machinery are not quite ready to handle such pseudos 993 live across such edges. */ 994 if (bb_has_abnormal_pred (bb)) 995 { 996 #ifdef STACK_REGS 997 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px) 998 lra_reg_info[px].no_stack_p = true; 999 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++) 1000 make_hard_regno_born (px, false); 1001 #endif 1002 /* No need to record conflicts for call clobbered regs if we 1003 have nonlocal labels around, as we don't ever try to 1004 allocate such regs in this case. */ 1005 if (!cfun->has_nonlocal_label 1006 && has_abnormal_call_or_eh_pred_edge_p (bb)) 1007 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++) 1008 if (call_used_regs[px] 1009 #ifdef REAL_PIC_OFFSET_TABLE_REGNUM 1010 /* We should create a conflict of PIC pseudo with PIC 1011 hard reg as PIC hard reg can have a wrong value after 1012 jump described by the abnormal edge. In this case we 1013 can not allocate PIC hard reg to PIC pseudo as PIC 1014 pseudo will also have a wrong value. */ 1015 || (px == REAL_PIC_OFFSET_TABLE_REGNUM 1016 && pic_offset_table_rtx != NULL_RTX 1017 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER) 1018 #endif 1019 ) 1020 make_hard_regno_born (px, false); 1021 } 1022 1023 bool live_change_p = false; 1024 /* Check if bb border live info was changed. */ 1025 unsigned int live_pseudos_num = 0; 1026 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 1027 FIRST_PSEUDO_REGISTER, j, bi) 1028 { 1029 live_pseudos_num++; 1030 if (! sparseset_bit_p (pseudos_live, j)) 1031 { 1032 live_change_p = true; 1033 if (lra_dump_file != NULL) 1034 fprintf (lra_dump_file, 1035 " r%d is removed as live at bb%d start\n", j, bb->index); 1036 break; 1037 } 1038 } 1039 if (! live_change_p 1040 && sparseset_cardinality (pseudos_live) != live_pseudos_num) 1041 { 1042 live_change_p = true; 1043 if (lra_dump_file != NULL) 1044 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j) 1045 if (! bitmap_bit_p (df_get_live_in (bb), j)) 1046 fprintf (lra_dump_file, 1047 " r%d is added to live at bb%d start\n", j, bb->index); 1048 } 1049 /* See if we'll need an increment at the end of this basic block. 1050 An increment is needed if the PSEUDOS_LIVE set is not empty, 1051 to make sure the finish points are set up correctly. */ 1052 need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0); 1053 1054 EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i) 1055 mark_pseudo_dead (i, curr_point); 1056 1057 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi) 1058 { 1059 if (sparseset_cardinality (pseudos_live_through_calls) == 0) 1060 break; 1061 if (sparseset_bit_p (pseudos_live_through_calls, j)) 1062 check_pseudos_live_through_calls (j, last_call_used_reg_set); 1063 } 1064 1065 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1066 { 1067 if (!TEST_HARD_REG_BIT (hard_regs_live, i)) 1068 continue; 1069 1070 if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i)) 1071 continue; 1072 1073 if (bitmap_bit_p (df_get_live_in (bb), i)) 1074 continue; 1075 1076 live_change_p = true; 1077 if (lra_dump_file) 1078 fprintf (lra_dump_file, 1079 " hard reg r%d is added to live at bb%d start\n", i, 1080 bb->index); 1081 bitmap_set_bit (df_get_live_in (bb), i); 1082 } 1083 1084 if (need_curr_point_incr) 1085 next_program_point (curr_point, freq); 1086 1087 return live_change_p; 1088 } 1089 1090 /* Compress pseudo live ranges by removing program points where 1091 nothing happens. Complexity of many algorithms in LRA is linear 1092 function of program points number. To speed up the code we try to 1093 minimize the number of the program points here. */ 1094 static void 1095 remove_some_program_points_and_update_live_ranges (void) 1096 { 1097 unsigned i; 1098 int n, max_regno; 1099 int *map; 1100 lra_live_range_t r, prev_r, next_r; 1101 sbitmap_iterator sbi; 1102 bool born_p, dead_p, prev_born_p, prev_dead_p; 1103 1104 auto_sbitmap born (lra_live_max_point); 1105 auto_sbitmap dead (lra_live_max_point); 1106 bitmap_clear (born); 1107 bitmap_clear (dead); 1108 max_regno = max_reg_num (); 1109 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++) 1110 { 1111 for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next) 1112 { 1113 lra_assert (r->start <= r->finish); 1114 bitmap_set_bit (born, r->start); 1115 bitmap_set_bit (dead, r->finish); 1116 } 1117 } 1118 auto_sbitmap born_or_dead (lra_live_max_point); 1119 bitmap_ior (born_or_dead, born, dead); 1120 map = XCNEWVEC (int, lra_live_max_point); 1121 n = -1; 1122 prev_born_p = prev_dead_p = false; 1123 EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi) 1124 { 1125 born_p = bitmap_bit_p (born, i); 1126 dead_p = bitmap_bit_p (dead, i); 1127 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p) 1128 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p)) 1129 { 1130 map[i] = n; 1131 lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]); 1132 } 1133 else 1134 { 1135 map[i] = ++n; 1136 lra_point_freq[n] = lra_point_freq[i]; 1137 } 1138 prev_born_p = born_p; 1139 prev_dead_p = dead_p; 1140 } 1141 n++; 1142 if (lra_dump_file != NULL) 1143 fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n", 1144 lra_live_max_point, n, 100 * n / lra_live_max_point); 1145 if (n < lra_live_max_point) 1146 { 1147 lra_live_max_point = n; 1148 for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++) 1149 { 1150 for (prev_r = NULL, r = lra_reg_info[i].live_ranges; 1151 r != NULL; 1152 r = next_r) 1153 { 1154 next_r = r->next; 1155 r->start = map[r->start]; 1156 r->finish = map[r->finish]; 1157 if (prev_r == NULL || prev_r->start > r->finish + 1) 1158 { 1159 prev_r = r; 1160 continue; 1161 } 1162 prev_r->start = r->start; 1163 prev_r->next = next_r; 1164 lra_live_range_pool.remove (r); 1165 } 1166 } 1167 } 1168 free (map); 1169 } 1170 1171 /* Print live ranges R to file F. */ 1172 void 1173 lra_print_live_range_list (FILE *f, lra_live_range_t r) 1174 { 1175 for (; r != NULL; r = r->next) 1176 fprintf (f, " [%d..%d]", r->start, r->finish); 1177 fprintf (f, "\n"); 1178 } 1179 1180 DEBUG_FUNCTION void 1181 debug (lra_live_range &ref) 1182 { 1183 lra_print_live_range_list (stderr, &ref); 1184 } 1185 1186 DEBUG_FUNCTION void 1187 debug (lra_live_range *ptr) 1188 { 1189 if (ptr) 1190 debug (*ptr); 1191 else 1192 fprintf (stderr, "<nil>\n"); 1193 } 1194 1195 /* Print live ranges R to stderr. */ 1196 void 1197 lra_debug_live_range_list (lra_live_range_t r) 1198 { 1199 lra_print_live_range_list (stderr, r); 1200 } 1201 1202 /* Print live ranges of pseudo REGNO to file F. */ 1203 static void 1204 print_pseudo_live_ranges (FILE *f, int regno) 1205 { 1206 if (lra_reg_info[regno].live_ranges == NULL) 1207 return; 1208 fprintf (f, " r%d:", regno); 1209 lra_print_live_range_list (f, lra_reg_info[regno].live_ranges); 1210 } 1211 1212 /* Print live ranges of pseudo REGNO to stderr. */ 1213 void 1214 lra_debug_pseudo_live_ranges (int regno) 1215 { 1216 print_pseudo_live_ranges (stderr, regno); 1217 } 1218 1219 /* Print live ranges of all pseudos to file F. */ 1220 static void 1221 print_live_ranges (FILE *f) 1222 { 1223 int i, max_regno; 1224 1225 max_regno = max_reg_num (); 1226 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 1227 print_pseudo_live_ranges (f, i); 1228 } 1229 1230 /* Print live ranges of all pseudos to stderr. */ 1231 void 1232 lra_debug_live_ranges (void) 1233 { 1234 print_live_ranges (stderr); 1235 } 1236 1237 /* Compress pseudo live ranges. */ 1238 static void 1239 compress_live_ranges (void) 1240 { 1241 remove_some_program_points_and_update_live_ranges (); 1242 if (lra_dump_file != NULL) 1243 { 1244 fprintf (lra_dump_file, "Ranges after the compression:\n"); 1245 print_live_ranges (lra_dump_file); 1246 } 1247 } 1248 1249 1250 1251 /* The number of the current live range pass. */ 1252 int lra_live_range_iter; 1253 1254 /* The function creates live ranges only for memory pseudos (or for 1255 all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It 1256 also does dead insn elimination if DEAD_INSN_P and global live 1257 analysis only for pseudos and only if the pseudo live info was 1258 changed on a BB border. Return TRUE if the live info was 1259 changed. */ 1260 static bool 1261 lra_create_live_ranges_1 (bool all_p, bool dead_insn_p) 1262 { 1263 basic_block bb; 1264 int i, hard_regno, max_regno = max_reg_num (); 1265 int curr_point; 1266 bool bb_live_change_p, have_referenced_pseudos = false; 1267 1268 timevar_push (TV_LRA_CREATE_LIVE_RANGES); 1269 1270 complete_info_p = all_p; 1271 if (lra_dump_file != NULL) 1272 fprintf (lra_dump_file, 1273 "\n********** Pseudo live ranges #%d: **********\n\n", 1274 ++lra_live_range_iter); 1275 memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage)); 1276 for (i = 0; i < max_regno; i++) 1277 { 1278 lra_reg_info[i].live_ranges = NULL; 1279 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs); 1280 lra_reg_info[i].preferred_hard_regno1 = -1; 1281 lra_reg_info[i].preferred_hard_regno2 = -1; 1282 lra_reg_info[i].preferred_hard_regno_profit1 = 0; 1283 lra_reg_info[i].preferred_hard_regno_profit2 = 0; 1284 #ifdef STACK_REGS 1285 lra_reg_info[i].no_stack_p = false; 1286 #endif 1287 /* The biggest mode is already set but its value might be to 1288 conservative because of recent transformation. Here in this 1289 file we recalculate it again as it costs practically 1290 nothing. */ 1291 if (i >= FIRST_PSEUDO_REGISTER && regno_reg_rtx[i] != NULL_RTX) 1292 lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]); 1293 else 1294 lra_reg_info[i].biggest_mode = VOIDmode; 1295 lra_reg_info[i].call_p = false; 1296 if (i >= FIRST_PSEUDO_REGISTER 1297 && lra_reg_info[i].nrefs != 0) 1298 { 1299 if ((hard_regno = reg_renumber[i]) >= 0) 1300 lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq; 1301 have_referenced_pseudos = true; 1302 } 1303 } 1304 lra_free_copies (); 1305 1306 /* Under some circumstances, we can have functions without pseudo 1307 registers. For such functions, lra_live_max_point will be 0, 1308 see e.g. PR55604, and there's nothing more to do for us here. */ 1309 if (! have_referenced_pseudos) 1310 { 1311 timevar_pop (TV_LRA_CREATE_LIVE_RANGES); 1312 return false; 1313 } 1314 1315 pseudos_live = sparseset_alloc (max_regno); 1316 pseudos_live_through_calls = sparseset_alloc (max_regno); 1317 pseudos_live_through_setjumps = sparseset_alloc (max_regno); 1318 start_living = sparseset_alloc (max_regno); 1319 start_dying = sparseset_alloc (max_regno); 1320 dead_set = sparseset_alloc (max_regno); 1321 unused_set = sparseset_alloc (max_regno); 1322 curr_point = 0; 1323 unsigned new_length = get_max_uid () * 2; 1324 point_freq_vec.truncate (0); 1325 point_freq_vec.reserve_exact (new_length); 1326 lra_point_freq = point_freq_vec.address (); 1327 auto_vec<int, 20> post_order_rev_cfg; 1328 inverted_post_order_compute (&post_order_rev_cfg); 1329 lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun)); 1330 bb_live_change_p = false; 1331 for (i = post_order_rev_cfg.length () - 1; i >= 0; --i) 1332 { 1333 bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]); 1334 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb 1335 == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 1336 continue; 1337 if (process_bb_lives (bb, curr_point, dead_insn_p)) 1338 bb_live_change_p = true; 1339 } 1340 if (bb_live_change_p) 1341 { 1342 /* We need to clear pseudo live info as some pseudos can 1343 disappear, e.g. pseudos with used equivalences. */ 1344 FOR_EACH_BB_FN (bb, cfun) 1345 { 1346 bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, 1347 max_regno - FIRST_PSEUDO_REGISTER); 1348 bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, 1349 max_regno - FIRST_PSEUDO_REGISTER); 1350 } 1351 /* As we did not change CFG since LRA start we can use 1352 DF-infrastructure solver to solve live data flow problem. */ 1353 for (int i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1354 { 1355 if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i)) 1356 bitmap_clear_bit (&all_hard_regs_bitmap, i); 1357 } 1358 df_simple_dataflow 1359 (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n, 1360 live_trans_fun, &all_blocks, 1361 df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD)); 1362 if (lra_dump_file != NULL) 1363 { 1364 fprintf (lra_dump_file, 1365 "Global pseudo live data have been updated:\n"); 1366 basic_block bb; 1367 FOR_EACH_BB_FN (bb, cfun) 1368 { 1369 bb_data_t bb_info = get_bb_data (bb); 1370 bitmap bb_livein = df_get_live_in (bb); 1371 bitmap bb_liveout = df_get_live_out (bb); 1372 1373 fprintf (lra_dump_file, "\nBB %d:\n", bb->index); 1374 lra_dump_bitmap_with_title (" gen:", 1375 &bb_info->gen_pseudos, bb->index); 1376 lra_dump_bitmap_with_title (" killed:", 1377 &bb_info->killed_pseudos, bb->index); 1378 lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index); 1379 lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index); 1380 } 1381 } 1382 } 1383 lra_live_max_point = curr_point; 1384 if (lra_dump_file != NULL) 1385 print_live_ranges (lra_dump_file); 1386 /* Clean up. */ 1387 sparseset_free (unused_set); 1388 sparseset_free (dead_set); 1389 sparseset_free (start_dying); 1390 sparseset_free (start_living); 1391 sparseset_free (pseudos_live_through_calls); 1392 sparseset_free (pseudos_live_through_setjumps); 1393 sparseset_free (pseudos_live); 1394 compress_live_ranges (); 1395 timevar_pop (TV_LRA_CREATE_LIVE_RANGES); 1396 return bb_live_change_p; 1397 } 1398 1399 /* The main entry function creates live-ranges and other live info 1400 necessary for the assignment sub-pass. It uses 1401 lra_creates_live_ranges_1 -- so read comments for the 1402 function. */ 1403 void 1404 lra_create_live_ranges (bool all_p, bool dead_insn_p) 1405 { 1406 if (! lra_create_live_ranges_1 (all_p, dead_insn_p)) 1407 return; 1408 if (lra_dump_file != NULL) 1409 fprintf (lra_dump_file, "Live info was changed -- recalculate it\n"); 1410 /* Live info was changed on a bb border. It means that some info, 1411 e.g. about conflict regs, calls crossed, and live ranges may be 1412 wrong. We need this info for allocation. So recalculate it 1413 again but without removing dead insns which can change live info 1414 again. Repetitive live range calculations are expensive therefore 1415 we stop here as we already have correct info although some 1416 improvement in rare cases could be possible on this sub-pass if 1417 we do dead insn elimination again (still the improvement may 1418 happen later). */ 1419 lra_clear_live_ranges (); 1420 bool res = lra_create_live_ranges_1 (all_p, false); 1421 lra_assert (! res); 1422 } 1423 1424 /* Finish all live ranges. */ 1425 void 1426 lra_clear_live_ranges (void) 1427 { 1428 int i; 1429 1430 for (i = 0; i < max_reg_num (); i++) 1431 free_live_range_list (lra_reg_info[i].live_ranges); 1432 point_freq_vec.release (); 1433 } 1434 1435 /* Initialize live ranges data once per function. */ 1436 void 1437 lra_live_ranges_init (void) 1438 { 1439 bitmap_initialize (&temp_bitmap, ®_obstack); 1440 initiate_live_solver (); 1441 } 1442 1443 /* Finish live ranges data once per function. */ 1444 void 1445 lra_live_ranges_finish (void) 1446 { 1447 finish_live_solver (); 1448 bitmap_clear (&temp_bitmap); 1449 lra_live_range_pool.release (); 1450 } 1451