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