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