1/* Rematerialize pseudos values. 2 Copyright (C) 2014-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/* This code objective is to rematerialize spilled pseudo values. To 22 do this we calculate available insn candidates. The candidate is 23 available at some point if there is dominated set of insns with the 24 same pattern, the insn inputs are not dying or modified on any path 25 from the set, the outputs are not modified. 26 27 The insns containing memory or spilled pseudos (except for the 28 rematerialized pseudo) are not considered as such insns are not 29 profitable in comparison with regular loads of spilled pseudo 30 values. That simplifies the implementation as we don't need to 31 deal with memory aliasing. 32 33 To speed up available candidate calculation, we calculate partially 34 available candidates first and use them for initialization of the 35 availability. That is because (partial) availability sets are 36 sparse. 37 38 The rematerialization sub-pass could be improved further in the 39 following ways: 40 41 o We could make longer live ranges of inputs in the 42 rematerialization candidates if their hard registers are not used 43 for other purposes. This could be complicated if we need to 44 update BB live info information as LRA does not use 45 DF-infrastructure for compile-time reasons. This problem could 46 be overcome if constrain making live ranges longer only in BB/EBB 47 scope. 48 o We could use cost-based decision to choose rematerialization insn 49 (currently all insns without memory is can be used). 50 o We could use other free hard regs for unused output pseudos in 51 rematerialization candidates although such cases probably will 52 be very rare. */ 53 54 55#include "config.h" 56#include "system.h" 57#include "coretypes.h" 58#include "tm.h" 59#include "hard-reg-set.h" 60#include "rtl.h" 61#include "rtl-error.h" 62#include "tm_p.h" 63#include "target.h" 64#include "insn-config.h" 65#include "recog.h" 66#include "output.h" 67#include "regs.h" 68#include "hashtab.h" 69#include "hash-set.h" 70#include "vec.h" 71#include "machmode.h" 72#include "input.h" 73#include "function.h" 74#include "symtab.h" 75#include "flags.h" 76#include "statistics.h" 77#include "double-int.h" 78#include "real.h" 79#include "fixed-value.h" 80#include "alias.h" 81#include "wide-int.h" 82#include "inchash.h" 83#include "tree.h" 84#include "expmed.h" 85#include "dojump.h" 86#include "explow.h" 87#include "calls.h" 88#include "emit-rtl.h" 89#include "varasm.h" 90#include "stmt.h" 91#include "expr.h" 92#include "predict.h" 93#include "dominance.h" 94#include "cfg.h" 95#include "basic-block.h" 96#include "except.h" 97#include "df.h" 98#include "ira.h" 99#include "sparseset.h" 100#include "params.h" 101#include "lra-int.h" 102 103/* Number of candidates for rematerialization. */ 104static unsigned int cands_num; 105 106/* The following is used for representation of call_used_reg_set in 107 form array whose elements are hard register numbers with nonzero bit 108 in CALL_USED_REG_SET. */ 109static int call_used_regs_arr_len; 110static int call_used_regs_arr[FIRST_PSEUDO_REGISTER]; 111 112/* Bitmap used for different calculations. */ 113static bitmap_head temp_bitmap; 114 115/* Registers accessed via subreg_p. */ 116static bitmap_head subreg_regs; 117 118typedef struct cand *cand_t; 119typedef const struct cand *const_cand_t; 120 121/* Insn candidates for rematerialization. The candidate insn should 122 have the following properies: 123 o no any memory (as access to memory is non-profitable) 124 o no INOUT regs (it means no non-paradoxical subreg of output reg) 125 o one output spilled pseudo (or reload pseudo of a spilled pseudo) 126 o all other pseudos are with assigned hard regs. */ 127struct cand 128{ 129 /* Index of the candidates in all_cands. */ 130 int index; 131 /* The candidate insn. */ 132 rtx_insn *insn; 133 /* Insn pseudo regno for rematerialization. */ 134 int regno; 135 /* Non-negative if a reload pseudo is in the insn instead of the 136 pseudo for rematerialization. */ 137 int reload_regno; 138 /* Number of the operand containing the regno or its reload 139 regno. */ 140 int nop; 141 /* Next candidate for the same regno. */ 142 cand_t next_regno_cand; 143}; 144 145/* Vector containing all candidates. */ 146static vec<cand_t> all_cands; 147/* Map: insn -> candidate representing it. It is null if the insn can 148 not be used for rematerialization. */ 149static cand_t *insn_to_cand; 150/* A secondary map, for candidates that involve two insns, where the 151 second one makes the equivalence. The candidate must not be used 152 before seeing this activation insn. */ 153static cand_t *insn_to_cand_activation; 154 155/* Map regno -> candidates can be used for the regno 156 rematerialization. */ 157static cand_t *regno_cands; 158 159/* Data about basic blocks used for the rematerialization 160 sub-pass. */ 161struct remat_bb_data 162{ 163 /* Basic block about which the below data are. */ 164 basic_block bb; 165 /* Registers changed in the basic block: */ 166 bitmap_head changed_regs; 167 /* Registers becoming dead in the BB. */ 168 bitmap_head dead_regs; 169 /* Cands present in the BB whose in/out regs are not changed after 170 the cands occurence and are not dead (except the reload 171 regno). */ 172 bitmap_head gen_cands; 173 bitmap_head livein_cands; /* cands whose inputs live at the BB start. */ 174 bitmap_head pavin_cands; /* cands partially available at BB entry. */ 175 bitmap_head pavout_cands; /* cands partially available at BB exit. */ 176 bitmap_head avin_cands; /* cands available at the entry of the BB. */ 177 bitmap_head avout_cands; /* cands available at the exit of the BB. */ 178}; 179 180/* Array for all BB data. Indexed by the corresponding BB index. */ 181typedef struct remat_bb_data *remat_bb_data_t; 182 183/* Basic blocks for data flow problems -- all bocks except the special 184 ones. */ 185static bitmap_head all_blocks; 186 187/* All basic block data are referred through the following array. */ 188static remat_bb_data_t remat_bb_data; 189 190/* Two small functions for access to the bb data. */ 191static inline remat_bb_data_t 192get_remat_bb_data (basic_block bb) 193{ 194 return &remat_bb_data[(bb)->index]; 195} 196 197static inline remat_bb_data_t 198get_remat_bb_data_by_index (int index) 199{ 200 return &remat_bb_data[index]; 201} 202 203 204 205/* Recursive hash function for RTL X. */ 206static hashval_t 207rtx_hash (rtx x) 208{ 209 int i, j; 210 enum rtx_code code; 211 const char *fmt; 212 hashval_t val = 0; 213 214 if (x == 0) 215 return val; 216 217 code = GET_CODE (x); 218 val += (int) code + 4095; 219 220 /* Some RTL can be compared nonrecursively. */ 221 switch (code) 222 { 223 case REG: 224 return val + REGNO (x); 225 226 case LABEL_REF: 227 return iterative_hash_object (XEXP (x, 0), val); 228 229 case SYMBOL_REF: 230 return iterative_hash_object (XSTR (x, 0), val); 231 232 case SCRATCH: 233 case CONST_DOUBLE: 234 case CONST_INT: 235 case CONST_VECTOR: 236 return val; 237 238 default: 239 break; 240 } 241 242 /* Hash the elements. */ 243 fmt = GET_RTX_FORMAT (code); 244 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 245 { 246 switch (fmt[i]) 247 { 248 case 'w': 249 val += XWINT (x, i); 250 break; 251 252 case 'n': 253 case 'i': 254 val += XINT (x, i); 255 break; 256 257 case 'V': 258 case 'E': 259 val += XVECLEN (x, i); 260 261 for (j = 0; j < XVECLEN (x, i); j++) 262 val += rtx_hash (XVECEXP (x, i, j)); 263 break; 264 265 case 'e': 266 val += rtx_hash (XEXP (x, i)); 267 break; 268 269 case 'S': 270 case 's': 271 val += htab_hash_string (XSTR (x, i)); 272 break; 273 274 case 'u': 275 case '0': 276 case 't': 277 break; 278 279 /* It is believed that rtx's at this level will never 280 contain anything but integers and other rtx's, except for 281 within LABEL_REFs and SYMBOL_REFs. */ 282 default: 283 abort (); 284 } 285 } 286 return val; 287} 288 289 290 291/* Hash table for the candidates. Different insns (e.g. structurally 292 the same insns or even insns with different unused output regs) can 293 be represented by the same candidate in the table. */ 294static htab_t cand_table; 295 296/* Hash function for candidate CAND. */ 297static hashval_t 298cand_hash (const void *cand) 299{ 300 const_cand_t c = (const_cand_t) cand; 301 lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn); 302 struct lra_static_insn_data *static_id = id->insn_static_data; 303 int nops = static_id->n_operands; 304 hashval_t hash = 0; 305 306 for (int i = 0; i < nops; i++) 307 if (i == c->nop) 308 hash = iterative_hash_object (c->regno, hash); 309 else if (static_id->operand[i].type == OP_IN) 310 hash = iterative_hash_object (*id->operand_loc[i], hash); 311 return hash; 312} 313 314/* Equal function for candidates CAND1 and CAND2. They are equal if 315 the corresponding candidate insns have the same code, the same 316 regno for rematerialization, the same input operands. */ 317static int 318cand_eq_p (const void *cand1, const void *cand2) 319{ 320 const_cand_t c1 = (const_cand_t) cand1; 321 const_cand_t c2 = (const_cand_t) cand2; 322 lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn); 323 lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn); 324 struct lra_static_insn_data *static_id1 = id1->insn_static_data; 325 int nops = static_id1->n_operands; 326 327 if (c1->regno != c2->regno 328 || INSN_CODE (c1->insn) < 0 329 || INSN_CODE (c1->insn) != INSN_CODE (c2->insn)) 330 return false; 331 gcc_assert (c1->nop == c2->nop); 332 for (int i = 0; i < nops; i++) 333 if (i != c1->nop && static_id1->operand[i].type == OP_IN 334 && *id1->operand_loc[i] != *id2->operand_loc[i]) 335 return false; 336 return true; 337} 338 339/* Insert candidate CAND into the table if it is not there yet. 340 Return candidate which is in the table. */ 341static cand_t 342insert_cand (cand_t cand) 343{ 344 void **entry_ptr; 345 346 entry_ptr = htab_find_slot (cand_table, cand, INSERT); 347 if (*entry_ptr == NULL) 348 *entry_ptr = (void *) cand; 349 return (cand_t) *entry_ptr; 350} 351 352/* Free candidate CAND memory. */ 353static void 354free_cand (void *cand) 355{ 356 free (cand); 357} 358 359/* Initiate the candidate table. */ 360static void 361initiate_cand_table (void) 362{ 363 cand_table = htab_create (8000, cand_hash, cand_eq_p, 364 (htab_del) free_cand); 365} 366 367/* Finish the candidate table. */ 368static void 369finish_cand_table (void) 370{ 371 htab_delete (cand_table); 372} 373 374 375 376/* Return true if X contains memory or some UNSPEC. We can not just 377 check insn operands as memory or unspec might be not an operand 378 itself but contain an operand. Insn with memory access is not 379 profitable for rematerialization. Rematerialization of UNSPEC 380 might result in wrong code generation as the UNPEC effect is 381 unknown (e.g. generating a label). */ 382static bool 383bad_for_rematerialization_p (rtx x) 384{ 385 int i, j; 386 const char *fmt; 387 enum rtx_code code; 388 389 if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE) 390 return true; 391 code = GET_CODE (x); 392 fmt = GET_RTX_FORMAT (code); 393 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 394 { 395 if (fmt[i] == 'e') 396 { 397 if (bad_for_rematerialization_p (XEXP (x, i))) 398 return true; 399 } 400 else if (fmt[i] == 'E') 401 { 402 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 403 if (bad_for_rematerialization_p (XVECEXP (x, i, j))) 404 return true; 405 } 406 } 407 return false; 408} 409 410/* If INSN can not be used for rematerialization, return negative 411 value. If INSN can be considered as a candidate for 412 rematerialization, return value which is the operand number of the 413 pseudo for which the insn can be used for rematerialization. Here 414 we consider the insns without any memory, spilled pseudo (except 415 for the rematerialization pseudo), or dying or unused regs. */ 416static int 417operand_to_remat (rtx_insn *insn) 418{ 419 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 420 struct lra_static_insn_data *static_id = id->insn_static_data; 421 struct lra_insn_reg *reg, *found_reg = NULL; 422 423 /* Don't rematerialize insns which can change PC. */ 424 if (JUMP_P (insn) || CALL_P (insn)) 425 return -1; 426 /* First find a pseudo which can be rematerialized. */ 427 for (reg = id->regs; reg != NULL; reg = reg->next) 428 { 429 /* True FRAME_POINTER_NEEDED might be because we can not follow 430 changing sp offsets, e.g. alloca is used. If the insn contains 431 stack pointer in such case, we can not rematerialize it as we 432 can not know sp offset at a rematerialization place. */ 433 if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed) 434 return -1; 435 else if (reg->type == OP_OUT && ! reg->subreg_p 436 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL) 437 { 438 /* We permits only one spilled reg. */ 439 if (found_reg != NULL) 440 return -1; 441 found_reg = reg; 442 } 443 /* IRA calculates conflicts separately for subregs of two words 444 pseudo. Even if the pseudo lives, e.g. one its subreg can be 445 used lately, another subreg hard register can be already used 446 for something else. In such case, it is not safe to 447 rematerialize the insn. */ 448 if (reg->regno >= FIRST_PSEUDO_REGISTER 449 && bitmap_bit_p (&subreg_regs, reg->regno)) 450 return -1; 451 } 452 if (found_reg == NULL) 453 return -1; 454 if (found_reg->regno < FIRST_PSEUDO_REGISTER) 455 return -1; 456 if (bad_for_rematerialization_p (PATTERN (insn))) 457 return -1; 458 /* Check the other regs are not spilled. */ 459 for (reg = id->regs; reg != NULL; reg = reg->next) 460 if (found_reg == reg) 461 continue; 462 else if (reg->type == OP_INOUT) 463 return -1; 464 else if (reg->regno >= FIRST_PSEUDO_REGISTER 465 && reg_renumber[reg->regno] < 0) 466 /* Another spilled reg. */ 467 return -1; 468 else if (reg->type == OP_IN) 469 { 470 if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 471 /* We don't want to make live ranges longer. */ 472 return -1; 473 /* Check that there is no output reg as the input one. */ 474 for (struct lra_insn_reg *reg2 = id->regs; 475 reg2 != NULL; 476 reg2 = reg2->next) 477 if (reg2->type == OP_OUT && reg->regno == reg2->regno) 478 return -1; 479 if (reg->regno < FIRST_PSEUDO_REGISTER) 480 for (struct lra_insn_reg *reg2 = static_id->hard_regs; 481 reg2 != NULL; 482 reg2 = reg2->next) 483 if (reg2->type == OP_OUT 484 && reg->regno <= reg2->regno 485 && (reg2->regno 486 < (reg->regno 487 + hard_regno_nregs[reg->regno][reg->biggest_mode]))) 488 return -1; 489 } 490 /* Find the rematerialization operand. */ 491 int nop = static_id->n_operands; 492 for (int i = 0; i < nop; i++) 493 if (REG_P (*id->operand_loc[i]) 494 && (int) REGNO (*id->operand_loc[i]) == found_reg->regno) 495 return i; 496 return -1; 497} 498 499/* Create candidate for INSN with rematerialization operand NOP and 500 REGNO. Insert the candidate into the table and set up the 501 corresponding INSN_TO_CAND element. */ 502static void 503create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL) 504{ 505 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 506 rtx reg = *id->operand_loc[nop]; 507 gcc_assert (REG_P (reg)); 508 int op_regno = REGNO (reg); 509 gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER); 510 cand_t cand = XNEW (struct cand); 511 cand->insn = insn; 512 cand->nop = nop; 513 cand->regno = regno; 514 cand->reload_regno = op_regno == regno ? -1 : op_regno; 515 gcc_assert (cand->regno >= 0); 516 cand_t cand_in_table = insert_cand (cand); 517 insn_to_cand[INSN_UID (insn)] = cand_in_table; 518 if (cand != cand_in_table) 519 free (cand); 520 else 521 { 522 /* A new cand. */ 523 cand->index = all_cands.length (); 524 all_cands.safe_push (cand); 525 cand->next_regno_cand = regno_cands[cand->regno]; 526 regno_cands[cand->regno] = cand; 527 } 528 if (activation) 529 insn_to_cand_activation[INSN_UID (activation)] = cand_in_table; 530} 531 532/* Create rematerialization candidates (inserting them into the 533 table). */ 534static void 535create_cands (void) 536{ 537 rtx_insn *insn; 538 struct potential_cand 539 { 540 rtx_insn *insn; 541 int nop; 542 }; 543 struct potential_cand *regno_potential_cand; 544 545 /* Create candidates. */ 546 regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ()); 547 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 548 if (NONDEBUG_INSN_P (insn)) 549 { 550 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 551 int keep_regno = -1; 552 rtx set = single_set (insn); 553 int nop; 554 555 /* See if this is an output reload for a previous insn. */ 556 if (set != NULL 557 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))) 558 { 559 rtx dstreg = SET_DEST (set); 560 int src_regno = REGNO (SET_SRC (set)); 561 int dst_regno = REGNO (dstreg); 562 rtx_insn *insn2 = regno_potential_cand[src_regno].insn; 563 564 if (insn2 != NULL 565 && dst_regno >= FIRST_PSEUDO_REGISTER 566 && reg_renumber[dst_regno] < 0 567 && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn)) 568 { 569 create_cand (insn2, regno_potential_cand[src_regno].nop, 570 dst_regno, insn); 571 goto done; 572 } 573 } 574 575 nop = operand_to_remat (insn); 576 if (nop >= 0) 577 { 578 gcc_assert (REG_P (*id->operand_loc[nop])); 579 int regno = REGNO (*id->operand_loc[nop]); 580 gcc_assert (regno >= FIRST_PSEUDO_REGISTER); 581 /* If we're setting an unrenumbered pseudo, make a candidate immediately. 582 If it's an output reload register, save it for later; the code above 583 looks for output reload insns later on. */ 584 if (reg_renumber[regno] < 0) 585 create_cand (insn, nop, regno); 586 else if (regno >= lra_constraint_new_regno_start) 587 { 588 regno_potential_cand[regno].insn = insn; 589 regno_potential_cand[regno].nop = nop; 590 keep_regno = regno; 591 } 592 } 593 594 done: 595 for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next) 596 if (reg->type != OP_IN && reg->regno != keep_regno 597 && reg->regno >= FIRST_PSEUDO_REGISTER) 598 regno_potential_cand[reg->regno].insn = NULL; 599 } 600 cands_num = all_cands.length (); 601 free (regno_potential_cand); 602} 603 604 605 606/* Create and initialize BB data. */ 607static void 608create_remat_bb_data (void) 609{ 610 basic_block bb; 611 remat_bb_data_t bb_info; 612 613 remat_bb_data = XNEWVEC (struct remat_bb_data, 614 last_basic_block_for_fn (cfun)); 615 FOR_ALL_BB_FN (bb, cfun) 616 { 617#ifdef ENABLE_CHECKING 618 if (bb->index < 0 || bb->index >= last_basic_block_for_fn (cfun)) 619 abort (); 620#endif 621 bb_info = get_remat_bb_data (bb); 622 bb_info->bb = bb; 623 bitmap_initialize (&bb_info->changed_regs, ®_obstack); 624 bitmap_initialize (&bb_info->dead_regs, ®_obstack); 625 bitmap_initialize (&bb_info->gen_cands, ®_obstack); 626 bitmap_initialize (&bb_info->livein_cands, ®_obstack); 627 bitmap_initialize (&bb_info->pavin_cands, ®_obstack); 628 bitmap_initialize (&bb_info->pavout_cands, ®_obstack); 629 bitmap_initialize (&bb_info->avin_cands, ®_obstack); 630 bitmap_initialize (&bb_info->avout_cands, ®_obstack); 631 } 632} 633 634/* Dump all candidates to DUMP_FILE. */ 635static void 636dump_cands (FILE *dump_file) 637{ 638 int i; 639 cand_t cand; 640 641 fprintf (dump_file, "\nCands:\n"); 642 for (i = 0; i < (int) cands_num; i++) 643 { 644 cand = all_cands[i]; 645 fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n", 646 i, cand->nop, cand->regno, cand->reload_regno); 647 print_inline_rtx (dump_file, cand->insn, 6); 648 fprintf (dump_file, "\n"); 649 } 650} 651 652/* Dump all candidates and BB data. */ 653static void 654dump_candidates_and_remat_bb_data (void) 655{ 656 basic_block bb; 657 658 if (lra_dump_file == NULL) 659 return; 660 dump_cands (lra_dump_file); 661 FOR_EACH_BB_FN (bb, cfun) 662 { 663 fprintf (lra_dump_file, "\nBB %d:\n", bb->index); 664 /* Livein */ 665 fprintf (lra_dump_file, " register live in:"); 666 dump_regset (df_get_live_in (bb), lra_dump_file); 667 putc ('\n', lra_dump_file); 668 /* Liveout */ 669 fprintf (lra_dump_file, " register live out:"); 670 dump_regset (df_get_live_out (bb), lra_dump_file); 671 putc ('\n', lra_dump_file); 672 /* Changed/dead regs: */ 673 fprintf (lra_dump_file, " changed regs:"); 674 dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file); 675 putc ('\n', lra_dump_file); 676 fprintf (lra_dump_file, " dead regs:"); 677 dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file); 678 putc ('\n', lra_dump_file); 679 lra_dump_bitmap_with_title ("cands generated in BB", 680 &get_remat_bb_data (bb)->gen_cands, bb->index); 681 lra_dump_bitmap_with_title ("livein cands in BB", 682 &get_remat_bb_data (bb)->livein_cands, bb->index); 683 lra_dump_bitmap_with_title ("pavin cands in BB", 684 &get_remat_bb_data (bb)->pavin_cands, bb->index); 685 lra_dump_bitmap_with_title ("pavout cands in BB", 686 &get_remat_bb_data (bb)->pavout_cands, bb->index); 687 lra_dump_bitmap_with_title ("avin cands in BB", 688 &get_remat_bb_data (bb)->avin_cands, bb->index); 689 lra_dump_bitmap_with_title ("avout cands in BB", 690 &get_remat_bb_data (bb)->avout_cands, bb->index); 691 } 692 fprintf (lra_dump_file, "subreg regs:"); 693 dump_regset (&subreg_regs, lra_dump_file); 694 putc ('\n', lra_dump_file); 695} 696 697/* Free all BB data. */ 698static void 699finish_remat_bb_data (void) 700{ 701 basic_block bb; 702 703 FOR_EACH_BB_FN (bb, cfun) 704 { 705 bitmap_clear (&get_remat_bb_data (bb)->avout_cands); 706 bitmap_clear (&get_remat_bb_data (bb)->avin_cands); 707 bitmap_clear (&get_remat_bb_data (bb)->pavout_cands); 708 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands); 709 bitmap_clear (&get_remat_bb_data (bb)->livein_cands); 710 bitmap_clear (&get_remat_bb_data (bb)->gen_cands); 711 bitmap_clear (&get_remat_bb_data (bb)->dead_regs); 712 bitmap_clear (&get_remat_bb_data (bb)->changed_regs); 713 } 714 free (remat_bb_data); 715} 716 717 718 719/* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */ 720static void 721set_bb_regs (basic_block bb, rtx_insn *insn) 722{ 723 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 724 remat_bb_data_t bb_info = get_remat_bb_data (bb); 725 struct lra_insn_reg *reg; 726 727 for (reg = id->regs; reg != NULL; reg = reg->next) 728 { 729 unsigned regno = reg->regno; 730 if (reg->type != OP_IN) 731 bitmap_set_bit (&bb_info->changed_regs, regno); 732 else if (find_regno_note (insn, REG_DEAD, regno) != NULL) 733 bitmap_set_bit (&bb_info->dead_regs, regno); 734 if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p) 735 bitmap_set_bit (&subreg_regs, regno); 736 } 737 if (CALL_P (insn)) 738 for (int i = 0; i < call_used_regs_arr_len; i++) 739 bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs, 740 call_used_regs_arr[i]); 741} 742 743/* Calculate changed_regs and dead_regs for each BB. */ 744static void 745calculate_local_reg_remat_bb_data (void) 746{ 747 basic_block bb; 748 rtx_insn *insn; 749 750 FOR_EACH_BB_FN (bb, cfun) 751 FOR_BB_INSNS (bb, insn) 752 if (NONDEBUG_INSN_P (insn)) 753 set_bb_regs (bb, insn); 754} 755 756 757 758/* Return true if REGNO is an input operand of INSN. */ 759static bool 760input_regno_present_p (rtx_insn *insn, int regno) 761{ 762 int iter; 763 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 764 struct lra_static_insn_data *static_id = id->insn_static_data; 765 struct lra_insn_reg *reg; 766 767 for (iter = 0; iter < 2; iter++) 768 for (reg = (iter == 0 ? id->regs : static_id->hard_regs); 769 reg != NULL; 770 reg = reg->next) 771 if (reg->type == OP_IN && reg->regno == regno) 772 return true; 773 return false; 774} 775 776/* Return true if a call used register is an input operand of INSN. */ 777static bool 778call_used_input_regno_present_p (rtx_insn *insn) 779{ 780 int iter; 781 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 782 struct lra_static_insn_data *static_id = id->insn_static_data; 783 struct lra_insn_reg *reg; 784 785 for (iter = 0; iter < 2; iter++) 786 for (reg = (iter == 0 ? id->regs : static_id->hard_regs); 787 reg != NULL; 788 reg = reg->next) 789 if (reg->type == OP_IN && reg->regno <= FIRST_PSEUDO_REGISTER 790 && TEST_HARD_REG_BIT (call_used_reg_set, reg->regno)) 791 return true; 792 return false; 793} 794 795/* Calculate livein_cands for each BB. */ 796static void 797calculate_livein_cands (void) 798{ 799 basic_block bb; 800 801 FOR_EACH_BB_FN (bb, cfun) 802 { 803 bitmap livein_regs = df_get_live_in (bb); 804 bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands; 805 for (unsigned int i = 0; i < cands_num; i++) 806 { 807 cand_t cand = all_cands[i]; 808 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn); 809 struct lra_insn_reg *reg; 810 811 for (reg = id->regs; reg != NULL; reg = reg->next) 812 if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno)) 813 break; 814 if (reg == NULL) 815 bitmap_set_bit (livein_cands, i); 816 } 817 } 818} 819 820/* Calculate gen_cands for each BB. */ 821static void 822calculate_gen_cands (void) 823{ 824 basic_block bb; 825 bitmap gen_cands; 826 bitmap_head gen_insns; 827 rtx_insn *insn; 828 829 bitmap_initialize (&gen_insns, ®_obstack); 830 FOR_EACH_BB_FN (bb, cfun) 831 { 832 gen_cands = &get_remat_bb_data (bb)->gen_cands; 833 bitmap_clear (&gen_insns); 834 FOR_BB_INSNS (bb, insn) 835 if (INSN_P (insn)) 836 { 837 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 838 struct lra_static_insn_data *static_id = id->insn_static_data; 839 struct lra_insn_reg *reg; 840 unsigned int uid; 841 bitmap_iterator bi; 842 cand_t cand; 843 rtx set; 844 int iter; 845 int src_regno = -1, dst_regno = -1; 846 847 if ((set = single_set (insn)) != NULL 848 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))) 849 { 850 src_regno = REGNO (SET_SRC (set)); 851 dst_regno = REGNO (SET_DEST (set)); 852 } 853 854 /* Update gen_cands: */ 855 bitmap_clear (&temp_bitmap); 856 for (iter = 0; iter < 2; iter++) 857 for (reg = (iter == 0 ? id->regs : static_id->hard_regs); 858 reg != NULL; 859 reg = reg->next) 860 if (reg->type != OP_IN 861 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 862 EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi) 863 { 864 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn; 865 866 cand = insn_to_cand[INSN_UID (insn2)]; 867 gcc_assert (cand != NULL); 868 /* Ignore the reload insn. */ 869 if (src_regno == cand->reload_regno 870 && dst_regno == cand->regno) 871 continue; 872 if (cand->regno == reg->regno 873 || input_regno_present_p (insn2, reg->regno)) 874 { 875 bitmap_clear_bit (gen_cands, cand->index); 876 bitmap_set_bit (&temp_bitmap, uid); 877 } 878 } 879 880 if (CALL_P (insn)) 881 EXECUTE_IF_SET_IN_BITMAP (&gen_insns, 0, uid, bi) 882 { 883 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn; 884 885 cand = insn_to_cand[INSN_UID (insn2)]; 886 gcc_assert (cand != NULL); 887 if (call_used_input_regno_present_p (insn2)) 888 { 889 bitmap_clear_bit (gen_cands, cand->index); 890 bitmap_set_bit (&temp_bitmap, uid); 891 } 892 } 893 bitmap_and_compl_into (&gen_insns, &temp_bitmap); 894 895 cand = insn_to_cand[INSN_UID (insn)]; 896 if (cand != NULL) 897 { 898 bitmap_set_bit (gen_cands, cand->index); 899 bitmap_set_bit (&gen_insns, INSN_UID (insn)); 900 } 901 } 902 } 903 bitmap_clear (&gen_insns); 904} 905 906 907 908/* The common transfer function used by the DF equation solver to 909 propagate (partial) availability info BB_IN to BB_OUT through block 910 with BB_INDEX according to the following equation: 911 912 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen 913*/ 914static bool 915cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out) 916{ 917 remat_bb_data_t bb_info; 918 bitmap bb_livein, bb_changed_regs, bb_dead_regs; 919 unsigned int cid; 920 bitmap_iterator bi; 921 922 bb_info = get_remat_bb_data_by_index (bb_index); 923 bb_livein = &bb_info->livein_cands; 924 bb_changed_regs = &bb_info->changed_regs; 925 bb_dead_regs = &bb_info->dead_regs; 926 /* Calculate killed avin cands -- cands whose regs are changed or 927 becoming dead in the BB. We calculate it here as we hope that 928 repeated calculations are compensated by smaller size of BB_IN in 929 comparison with all candidates number. */ 930 bitmap_clear (&temp_bitmap); 931 EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi) 932 { 933 cand_t cand = all_cands[cid]; 934 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn); 935 struct lra_insn_reg *reg; 936 937 if (! bitmap_bit_p (bb_livein, cid)) 938 { 939 bitmap_set_bit (&temp_bitmap, cid); 940 continue; 941 } 942 for (reg = id->regs; reg != NULL; reg = reg->next) 943 /* Ignore all outputs which are not the regno for 944 rematerialization. */ 945 if (reg->type == OP_OUT && reg->regno != cand->regno) 946 continue; 947 else if (bitmap_bit_p (bb_changed_regs, reg->regno) 948 || bitmap_bit_p (bb_dead_regs, reg->regno)) 949 { 950 bitmap_set_bit (&temp_bitmap, cid); 951 break; 952 } 953 /* Check regno for rematerialization. */ 954 if (bitmap_bit_p (bb_changed_regs, cand->regno) 955 || bitmap_bit_p (bb_dead_regs, cand->regno)) 956 bitmap_set_bit (&temp_bitmap, cid); 957 } 958 return bitmap_ior_and_compl (bb_out, 959 &bb_info->gen_cands, bb_in, &temp_bitmap); 960} 961 962 963 964/* The transfer function used by the DF equation solver to propagate 965 partial candidate availability info through block with BB_INDEX 966 according to the following equation: 967 968 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen 969*/ 970static bool 971cand_pav_trans_fun (int bb_index) 972{ 973 remat_bb_data_t bb_info; 974 975 bb_info = get_remat_bb_data_by_index (bb_index); 976 return cand_trans_fun (bb_index, &bb_info->pavin_cands, 977 &bb_info->pavout_cands); 978} 979 980/* The confluence function used by the DF equation solver to set up 981 cand_pav info for a block BB without predecessor. */ 982static void 983cand_pav_con_fun_0 (basic_block bb) 984{ 985 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands); 986} 987 988/* The confluence function used by the DF equation solver to propagate 989 partial candidate availability info from predecessor to successor 990 on edge E (pred->bb) according to the following equation: 991 992 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors) 993 */ 994static bool 995cand_pav_con_fun_n (edge e) 996{ 997 basic_block pred = e->src; 998 basic_block bb = e->dest; 999 remat_bb_data_t bb_info; 1000 bitmap bb_pavin, pred_pavout; 1001 1002 bb_info = get_remat_bb_data (bb); 1003 bb_pavin = &bb_info->pavin_cands; 1004 pred_pavout = &get_remat_bb_data (pred)->pavout_cands; 1005 return bitmap_ior_into (bb_pavin, pred_pavout); 1006} 1007 1008 1009 1010/* The transfer function used by the DF equation solver to propagate 1011 candidate availability info through block with BB_INDEX according 1012 to the following equation: 1013 1014 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen 1015*/ 1016static bool 1017cand_av_trans_fun (int bb_index) 1018{ 1019 remat_bb_data_t bb_info; 1020 1021 bb_info = get_remat_bb_data_by_index (bb_index); 1022 return cand_trans_fun (bb_index, &bb_info->avin_cands, 1023 &bb_info->avout_cands); 1024} 1025 1026/* The confluence function used by the DF equation solver to set up 1027 cand_av info for a block BB without predecessor. */ 1028static void 1029cand_av_con_fun_0 (basic_block bb) 1030{ 1031 bitmap_clear (&get_remat_bb_data (bb)->avin_cands); 1032} 1033 1034/* The confluence function used by the DF equation solver to propagate 1035 cand_av info from predecessor to successor on edge E (pred->bb) 1036 according to the following equation: 1037 1038 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors) 1039 */ 1040static bool 1041cand_av_con_fun_n (edge e) 1042{ 1043 basic_block pred = e->src; 1044 basic_block bb = e->dest; 1045 remat_bb_data_t bb_info; 1046 bitmap bb_avin, pred_avout; 1047 1048 bb_info = get_remat_bb_data (bb); 1049 bb_avin = &bb_info->avin_cands; 1050 pred_avout = &get_remat_bb_data (pred)->avout_cands; 1051 return bitmap_and_into (bb_avin, pred_avout); 1052} 1053 1054/* Calculate available candidates for each BB. */ 1055static void 1056calculate_global_remat_bb_data (void) 1057{ 1058 basic_block bb; 1059 1060 df_simple_dataflow 1061 (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n, 1062 cand_pav_trans_fun, &all_blocks, 1063 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD)); 1064 /* Initialize avin by pavin. */ 1065 FOR_EACH_BB_FN (bb, cfun) 1066 bitmap_copy (&get_remat_bb_data (bb)->avin_cands, 1067 &get_remat_bb_data (bb)->pavin_cands); 1068 df_simple_dataflow 1069 (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n, 1070 cand_av_trans_fun, &all_blocks, 1071 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD)); 1072} 1073 1074 1075 1076/* Setup sp offset attribute to SP_OFFSET for all INSNS. */ 1077static void 1078change_sp_offset (rtx_insn *insns, HOST_WIDE_INT sp_offset) 1079{ 1080 for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn)) 1081 eliminate_regs_in_insn (insn, false, false, sp_offset); 1082} 1083 1084/* Return start hard register of REG (can be a hard or a pseudo reg) 1085 or -1 (if it is a spilled pseudo). Return number of hard registers 1086 occupied by REG through parameter NREGS if the start hard reg is 1087 not negative. */ 1088static int 1089get_hard_regs (struct lra_insn_reg *reg, int &nregs) 1090{ 1091 int regno = reg->regno; 1092 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno]; 1093 1094 if (hard_regno >= 0) 1095 nregs = hard_regno_nregs[hard_regno][reg->biggest_mode]; 1096 return hard_regno; 1097} 1098 1099/* Make copy of and register scratch pseudos in rematerialized insn 1100 REMAT_INSN. */ 1101static void 1102update_scratch_ops (rtx_insn *remat_insn) 1103{ 1104 lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn); 1105 struct lra_static_insn_data *static_id = id->insn_static_data; 1106 for (int i = 0; i < static_id->n_operands; i++) 1107 { 1108 rtx *loc = id->operand_loc[i]; 1109 if (! REG_P (*loc)) 1110 continue; 1111 int regno = REGNO (*loc); 1112 if (! lra_former_scratch_p (regno)) 1113 continue; 1114 *loc = lra_create_new_reg (GET_MODE (*loc), *loc, 1115 lra_get_allocno_class (regno), 1116 "scratch pseudo copy"); 1117 lra_register_new_scratch_op (remat_insn, i); 1118 } 1119 1120} 1121 1122/* Insert rematerialization insns using the data-flow data calculated 1123 earlier. */ 1124static bool 1125do_remat (void) 1126{ 1127 rtx_insn *insn; 1128 basic_block bb; 1129 bitmap_head avail_cands; 1130 bitmap_head active_cands; 1131 bool changed_p = false; 1132 /* Living hard regs and hard registers of living pseudos. */ 1133 HARD_REG_SET live_hard_regs; 1134 1135 bitmap_initialize (&avail_cands, ®_obstack); 1136 bitmap_initialize (&active_cands, ®_obstack); 1137 FOR_EACH_BB_FN (bb, cfun) 1138 { 1139 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_out (bb)); 1140 bitmap_and (&avail_cands, &get_remat_bb_data (bb)->avin_cands, 1141 &get_remat_bb_data (bb)->livein_cands); 1142 /* Activating insns are always in the same block as their corresponding 1143 remat insn, so at the start of a block the two bitsets are equal. */ 1144 bitmap_copy (&active_cands, &avail_cands); 1145 FOR_BB_INSNS (bb, insn) 1146 { 1147 if (!NONDEBUG_INSN_P (insn)) 1148 continue; 1149 1150 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 1151 struct lra_static_insn_data *static_id = id->insn_static_data; 1152 struct lra_insn_reg *reg; 1153 cand_t cand; 1154 unsigned int cid; 1155 bitmap_iterator bi; 1156 rtx set; 1157 int iter; 1158 int src_regno = -1, dst_regno = -1; 1159 1160 if ((set = single_set (insn)) != NULL 1161 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))) 1162 { 1163 src_regno = REGNO (SET_SRC (set)); 1164 dst_regno = REGNO (SET_DEST (set)); 1165 } 1166 1167 cand = NULL; 1168 /* Check possibility of rematerialization (hard reg or 1169 unpsilled pseudo <- spilled pseudo): */ 1170 if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER 1171 && reg_renumber[src_regno] < 0 1172 && (dst_regno < FIRST_PSEUDO_REGISTER 1173 || reg_renumber[dst_regno] >= 0)) 1174 { 1175 for (cand = regno_cands[src_regno]; 1176 cand != NULL; 1177 cand = cand->next_regno_cand) 1178 if (bitmap_bit_p (&avail_cands, cand->index) 1179 && bitmap_bit_p (&active_cands, cand->index)) 1180 break; 1181 } 1182 int i, hard_regno, nregs; 1183 rtx_insn *remat_insn = NULL; 1184 HOST_WIDE_INT cand_sp_offset = 0; 1185 if (cand != NULL) 1186 { 1187 lra_insn_recog_data_t cand_id 1188 = lra_get_insn_recog_data (cand->insn); 1189 struct lra_static_insn_data *static_cand_id 1190 = cand_id->insn_static_data; 1191 rtx saved_op = *cand_id->operand_loc[cand->nop]; 1192 1193 /* Check clobbers do not kill something living. */ 1194 gcc_assert (REG_P (saved_op)); 1195 int ignore_regno = REGNO (saved_op); 1196 1197 for (reg = cand_id->regs; reg != NULL; reg = reg->next) 1198 if (reg->type != OP_IN && reg->regno != ignore_regno) 1199 { 1200 hard_regno = get_hard_regs (reg, nregs); 1201 gcc_assert (hard_regno >= 0); 1202 for (i = 0; i < nregs; i++) 1203 if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i)) 1204 break; 1205 if (i < nregs) 1206 break; 1207 } 1208 1209 if (reg == NULL) 1210 { 1211 for (reg = static_cand_id->hard_regs; 1212 reg != NULL; 1213 reg = reg->next) 1214 if (reg->type != OP_IN 1215 && TEST_HARD_REG_BIT (live_hard_regs, reg->regno)) 1216 break; 1217 } 1218 1219 if (reg == NULL) 1220 { 1221 *cand_id->operand_loc[cand->nop] = SET_DEST (set); 1222 lra_update_insn_regno_info (cand->insn); 1223 bool ok_p = lra_constrain_insn (cand->insn); 1224 if (ok_p) 1225 { 1226 rtx remat_pat = copy_insn (PATTERN (cand->insn)); 1227 1228 start_sequence (); 1229 emit_insn (remat_pat); 1230 remat_insn = get_insns (); 1231 end_sequence (); 1232 if (recog_memoized (remat_insn) < 0) 1233 remat_insn = NULL; 1234 cand_sp_offset = cand_id->sp_offset; 1235 } 1236 *cand_id->operand_loc[cand->nop] = saved_op; 1237 lra_update_insn_regno_info (cand->insn); 1238 } 1239 } 1240 1241 bitmap_clear (&temp_bitmap); 1242 /* Update avail_cands (see analogous code for 1243 calculate_gen_cands). */ 1244 for (iter = 0; iter < 2; iter++) 1245 for (reg = (iter == 0 ? id->regs : static_id->hard_regs); 1246 reg != NULL; 1247 reg = reg->next) 1248 if (reg->type != OP_IN 1249 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1250 EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi) 1251 { 1252 cand = all_cands[cid]; 1253 1254 /* Ignore the reload insn. */ 1255 if (src_regno == cand->reload_regno 1256 && dst_regno == cand->regno) 1257 continue; 1258 if (cand->regno == reg->regno 1259 || input_regno_present_p (cand->insn, reg->regno)) 1260 bitmap_set_bit (&temp_bitmap, cand->index); 1261 } 1262 1263 if (CALL_P (insn)) 1264 EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi) 1265 { 1266 cand = all_cands[cid]; 1267 1268 if (call_used_input_regno_present_p (cand->insn)) 1269 bitmap_set_bit (&temp_bitmap, cand->index); 1270 } 1271 1272 bitmap_and_compl_into (&avail_cands, &temp_bitmap); 1273 1274 /* Now see whether a candidate is made active or available 1275 by this insn. */ 1276 cand = insn_to_cand_activation[INSN_UID (insn)]; 1277 if (cand) 1278 bitmap_set_bit (&active_cands, cand->index); 1279 1280 cand = insn_to_cand[INSN_UID (insn)]; 1281 if (cand != NULL) 1282 { 1283 bitmap_set_bit (&avail_cands, cand->index); 1284 if (cand->reload_regno == -1) 1285 bitmap_set_bit (&active_cands, cand->index); 1286 else 1287 bitmap_clear_bit (&active_cands, cand->index); 1288 } 1289 1290 if (remat_insn != NULL) 1291 { 1292 HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset; 1293 if (sp_offset_change != 0) 1294 change_sp_offset (remat_insn, sp_offset_change); 1295 update_scratch_ops (remat_insn); 1296 lra_process_new_insns (insn, remat_insn, NULL, 1297 "Inserting rematerialization insn"); 1298 lra_set_insn_deleted (insn); 1299 changed_p = true; 1300 continue; 1301 } 1302 1303 /* Update live hard regs: */ 1304 for (reg = id->regs; reg != NULL; reg = reg->next) 1305 if (reg->type == OP_IN 1306 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1307 { 1308 if ((hard_regno = get_hard_regs (reg, nregs)) < 0) 1309 continue; 1310 for (i = 0; i < nregs; i++) 1311 CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i); 1312 } 1313 /* Process also hard regs (e.g. CC register) which are part 1314 of insn definition. */ 1315 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next) 1316 if (reg->type == OP_IN 1317 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1318 CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno); 1319 /* Inputs have been processed, now process outputs. */ 1320 for (reg = id->regs; reg != NULL; reg = reg->next) 1321 if (reg->type != OP_IN 1322 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL) 1323 { 1324 if ((hard_regno = get_hard_regs (reg, nregs)) < 0) 1325 continue; 1326 for (i = 0; i < nregs; i++) 1327 SET_HARD_REG_BIT (live_hard_regs, hard_regno + i); 1328 } 1329 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next) 1330 if (reg->type != OP_IN 1331 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL) 1332 SET_HARD_REG_BIT (live_hard_regs, reg->regno); 1333 } 1334 } 1335 bitmap_clear (&avail_cands); 1336 bitmap_clear (&active_cands); 1337 return changed_p; 1338} 1339 1340 1341 1342/* Current number of rematerialization iteration. */ 1343int lra_rematerialization_iter; 1344 1345/* Entry point of the rematerialization sub-pass. Return true if we 1346 did any rematerialization. */ 1347bool 1348lra_remat (void) 1349{ 1350 basic_block bb; 1351 bool result; 1352 int max_regno = max_reg_num (); 1353 1354 if (! flag_lra_remat) 1355 return false; 1356 lra_rematerialization_iter++; 1357 if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES) 1358 return false; 1359 if (lra_dump_file != NULL) 1360 fprintf (lra_dump_file, 1361 "\n******** Rematerialization #%d: ********\n\n", 1362 lra_rematerialization_iter); 1363 timevar_push (TV_LRA_REMAT); 1364 insn_to_cand = XCNEWVEC (cand_t, get_max_uid ()); 1365 insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ()); 1366 regno_cands = XCNEWVEC (cand_t, max_regno); 1367 all_cands.create (8000); 1368 call_used_regs_arr_len = 0; 1369 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1370 if (call_used_regs[i]) 1371 call_used_regs_arr[call_used_regs_arr_len++] = i; 1372 initiate_cand_table (); 1373 create_remat_bb_data (); 1374 bitmap_initialize (&temp_bitmap, ®_obstack); 1375 bitmap_initialize (&subreg_regs, ®_obstack); 1376 calculate_local_reg_remat_bb_data (); 1377 create_cands (); 1378 calculate_livein_cands (); 1379 calculate_gen_cands (); 1380 bitmap_initialize (&all_blocks, ®_obstack); 1381 FOR_ALL_BB_FN (bb, cfun) 1382 bitmap_set_bit (&all_blocks, bb->index); 1383 calculate_global_remat_bb_data (); 1384 dump_candidates_and_remat_bb_data (); 1385 result = do_remat (); 1386 all_cands.release (); 1387 bitmap_clear (&temp_bitmap); 1388 bitmap_clear (&subreg_regs); 1389 finish_remat_bb_data (); 1390 finish_cand_table (); 1391 bitmap_clear (&all_blocks); 1392 free (regno_cands); 1393 free (insn_to_cand); 1394 free (insn_to_cand_activation); 1395 timevar_pop (TV_LRA_REMAT); 1396 return result; 1397} 1398