1 /* Rematerialize pseudos values. 2 Copyright (C) 2014-2015 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 /* 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. */ 104 static 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. */ 109 static int call_used_regs_arr_len; 110 static int call_used_regs_arr[FIRST_PSEUDO_REGISTER]; 111 112 /* Bitmap used for different calculations. */ 113 static bitmap_head temp_bitmap; 114 115 /* Registers accessed via subreg_p. */ 116 static bitmap_head subreg_regs; 117 118 typedef struct cand *cand_t; 119 typedef 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. */ 127 struct 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. */ 146 static vec<cand_t> all_cands; 147 /* Map: insn -> candidate representing it. It is null if the insn can 148 not be used for rematerialization. */ 149 static 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. */ 153 static cand_t *insn_to_cand_activation; 154 155 /* Map regno -> candidates can be used for the regno 156 rematerialization. */ 157 static cand_t *regno_cands; 158 159 /* Data about basic blocks used for the rematerialization 160 sub-pass. */ 161 struct 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. */ 181 typedef struct remat_bb_data *remat_bb_data_t; 182 183 /* Basic blocks for data flow problems -- all bocks except the special 184 ones. */ 185 static bitmap_head all_blocks; 186 187 /* All basic block data are referred through the following array. */ 188 static remat_bb_data_t remat_bb_data; 189 190 /* Two small functions for access to the bb data. */ 191 static inline remat_bb_data_t 192 get_remat_bb_data (basic_block bb) 193 { 194 return &remat_bb_data[(bb)->index]; 195 } 196 197 static inline remat_bb_data_t 198 get_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. */ 206 static hashval_t 207 rtx_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. */ 294 static htab_t cand_table; 295 296 /* Hash function for candidate CAND. */ 297 static hashval_t 298 cand_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. */ 317 static int 318 cand_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. */ 341 static cand_t 342 insert_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. */ 353 static void 354 free_cand (void *cand) 355 { 356 free (cand); 357 } 358 359 /* Initiate the candidate table. */ 360 static void 361 initiate_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. */ 368 static void 369 finish_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). */ 382 static bool 383 bad_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. */ 416 static int 417 operand_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. */ 502 static void 503 create_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). */ 534 static void 535 create_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. */ 607 static void 608 create_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. */ 635 static void 636 dump_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. */ 653 static void 654 dump_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. */ 698 static void 699 finish_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. */ 720 static void 721 set_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. */ 744 static void 745 calculate_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. */ 759 static bool 760 input_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. */ 777 static bool 778 call_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. */ 796 static void 797 calculate_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. */ 821 static void 822 calculate_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 */ 914 static bool 915 cand_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 */ 970 static bool 971 cand_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. */ 982 static void 983 cand_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 */ 994 static bool 995 cand_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 */ 1016 static bool 1017 cand_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. */ 1028 static void 1029 cand_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 */ 1040 static bool 1041 cand_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. */ 1055 static void 1056 calculate_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. */ 1077 static void 1078 change_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. */ 1088 static int 1089 get_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. */ 1101 static void 1102 update_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. */ 1124 static bool 1125 do_remat (void) 1126 { 1127 unsigned regno; 1128 rtx_insn *insn; 1129 basic_block bb; 1130 bitmap_head avail_cands; 1131 bitmap_head active_cands; 1132 bool changed_p = false; 1133 /* Living hard regs and hard registers of living pseudos. */ 1134 HARD_REG_SET live_hard_regs; 1135 bitmap_iterator bi; 1136 1137 bitmap_initialize (&avail_cands, ®_obstack); 1138 bitmap_initialize (&active_cands, ®_obstack); 1139 FOR_EACH_BB_FN (bb, cfun) 1140 { 1141 CLEAR_HARD_REG_SET (live_hard_regs); 1142 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi) 1143 { 1144 int hard_regno = regno < FIRST_PSEUDO_REGISTER 1145 ? regno 1146 : reg_renumber[regno]; 1147 if (hard_regno >= 0) 1148 SET_HARD_REG_BIT (live_hard_regs, hard_regno); 1149 } 1150 bitmap_and (&avail_cands, &get_remat_bb_data (bb)->avin_cands, 1151 &get_remat_bb_data (bb)->livein_cands); 1152 /* Activating insns are always in the same block as their corresponding 1153 remat insn, so at the start of a block the two bitsets are equal. */ 1154 bitmap_copy (&active_cands, &avail_cands); 1155 FOR_BB_INSNS (bb, insn) 1156 { 1157 if (!NONDEBUG_INSN_P (insn)) 1158 continue; 1159 1160 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn); 1161 struct lra_static_insn_data *static_id = id->insn_static_data; 1162 struct lra_insn_reg *reg; 1163 cand_t cand; 1164 unsigned int cid; 1165 bitmap_iterator bi; 1166 rtx set; 1167 int iter; 1168 int src_regno = -1, dst_regno = -1; 1169 1170 if ((set = single_set (insn)) != NULL 1171 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set))) 1172 { 1173 src_regno = REGNO (SET_SRC (set)); 1174 dst_regno = REGNO (SET_DEST (set)); 1175 } 1176 1177 cand = NULL; 1178 /* Check possibility of rematerialization (hard reg or 1179 unpsilled pseudo <- spilled pseudo): */ 1180 if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER 1181 && reg_renumber[src_regno] < 0 1182 && (dst_regno < FIRST_PSEUDO_REGISTER 1183 || reg_renumber[dst_regno] >= 0)) 1184 { 1185 for (cand = regno_cands[src_regno]; 1186 cand != NULL; 1187 cand = cand->next_regno_cand) 1188 if (bitmap_bit_p (&avail_cands, cand->index) 1189 && bitmap_bit_p (&active_cands, cand->index)) 1190 break; 1191 } 1192 int i, hard_regno, nregs; 1193 rtx_insn *remat_insn = NULL; 1194 HOST_WIDE_INT cand_sp_offset = 0; 1195 if (cand != NULL) 1196 { 1197 lra_insn_recog_data_t cand_id 1198 = lra_get_insn_recog_data (cand->insn); 1199 struct lra_static_insn_data *static_cand_id 1200 = cand_id->insn_static_data; 1201 rtx saved_op = *cand_id->operand_loc[cand->nop]; 1202 1203 /* Check clobbers do not kill something living. */ 1204 gcc_assert (REG_P (saved_op)); 1205 int ignore_regno = REGNO (saved_op); 1206 1207 for (reg = cand_id->regs; reg != NULL; reg = reg->next) 1208 if (reg->type != OP_IN && reg->regno != ignore_regno) 1209 { 1210 hard_regno = get_hard_regs (reg, nregs); 1211 gcc_assert (hard_regno >= 0); 1212 for (i = 0; i < nregs; i++) 1213 if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i)) 1214 break; 1215 if (i < nregs) 1216 break; 1217 } 1218 1219 if (reg == NULL) 1220 { 1221 for (reg = static_cand_id->hard_regs; 1222 reg != NULL; 1223 reg = reg->next) 1224 if (reg->type != OP_IN 1225 && TEST_HARD_REG_BIT (live_hard_regs, reg->regno)) 1226 break; 1227 } 1228 1229 if (reg == NULL) 1230 { 1231 *cand_id->operand_loc[cand->nop] = SET_DEST (set); 1232 lra_update_insn_regno_info (cand->insn); 1233 bool ok_p = lra_constrain_insn (cand->insn); 1234 if (ok_p) 1235 { 1236 rtx remat_pat = copy_insn (PATTERN (cand->insn)); 1237 1238 start_sequence (); 1239 emit_insn (remat_pat); 1240 remat_insn = get_insns (); 1241 end_sequence (); 1242 if (recog_memoized (remat_insn) < 0) 1243 remat_insn = NULL; 1244 cand_sp_offset = cand_id->sp_offset; 1245 } 1246 *cand_id->operand_loc[cand->nop] = saved_op; 1247 lra_update_insn_regno_info (cand->insn); 1248 } 1249 } 1250 1251 bitmap_clear (&temp_bitmap); 1252 /* Update avail_cands (see analogous code for 1253 calculate_gen_cands). */ 1254 for (iter = 0; iter < 2; iter++) 1255 for (reg = (iter == 0 ? id->regs : static_id->hard_regs); 1256 reg != NULL; 1257 reg = reg->next) 1258 if (reg->type != OP_IN 1259 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1260 EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi) 1261 { 1262 cand = all_cands[cid]; 1263 1264 /* Ignore the reload insn. */ 1265 if (src_regno == cand->reload_regno 1266 && dst_regno == cand->regno) 1267 continue; 1268 if (cand->regno == reg->regno 1269 || input_regno_present_p (cand->insn, reg->regno)) 1270 bitmap_set_bit (&temp_bitmap, cand->index); 1271 } 1272 1273 if (CALL_P (insn)) 1274 EXECUTE_IF_SET_IN_BITMAP (&avail_cands, 0, cid, bi) 1275 { 1276 cand = all_cands[cid]; 1277 1278 if (call_used_input_regno_present_p (cand->insn)) 1279 bitmap_set_bit (&temp_bitmap, cand->index); 1280 } 1281 1282 bitmap_and_compl_into (&avail_cands, &temp_bitmap); 1283 1284 /* Now see whether a candidate is made active or available 1285 by this insn. */ 1286 cand = insn_to_cand_activation[INSN_UID (insn)]; 1287 if (cand) 1288 bitmap_set_bit (&active_cands, cand->index); 1289 1290 cand = insn_to_cand[INSN_UID (insn)]; 1291 if (cand != NULL) 1292 { 1293 bitmap_set_bit (&avail_cands, cand->index); 1294 if (cand->reload_regno == -1) 1295 bitmap_set_bit (&active_cands, cand->index); 1296 else 1297 bitmap_clear_bit (&active_cands, cand->index); 1298 } 1299 1300 if (remat_insn != NULL) 1301 { 1302 HOST_WIDE_INT sp_offset_change = cand_sp_offset - id->sp_offset; 1303 if (sp_offset_change != 0) 1304 change_sp_offset (remat_insn, sp_offset_change); 1305 update_scratch_ops (remat_insn); 1306 lra_process_new_insns (insn, remat_insn, NULL, 1307 "Inserting rematerialization insn"); 1308 lra_set_insn_deleted (insn); 1309 changed_p = true; 1310 continue; 1311 } 1312 1313 /* Update live hard regs: */ 1314 for (reg = id->regs; reg != NULL; reg = reg->next) 1315 if (reg->type == OP_IN 1316 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1317 { 1318 if ((hard_regno = get_hard_regs (reg, nregs)) < 0) 1319 continue; 1320 for (i = 0; i < nregs; i++) 1321 CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i); 1322 } 1323 /* Process also hard regs (e.g. CC register) which are part 1324 of insn definition. */ 1325 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next) 1326 if (reg->type == OP_IN 1327 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL) 1328 CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno); 1329 /* Inputs have been processed, now process outputs. */ 1330 for (reg = id->regs; reg != NULL; reg = reg->next) 1331 if (reg->type != OP_IN 1332 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL) 1333 { 1334 if ((hard_regno = get_hard_regs (reg, nregs)) < 0) 1335 continue; 1336 for (i = 0; i < nregs; i++) 1337 SET_HARD_REG_BIT (live_hard_regs, hard_regno + i); 1338 } 1339 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next) 1340 if (reg->type != OP_IN 1341 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL) 1342 SET_HARD_REG_BIT (live_hard_regs, reg->regno); 1343 } 1344 } 1345 bitmap_clear (&avail_cands); 1346 bitmap_clear (&active_cands); 1347 return changed_p; 1348 } 1349 1350 1351 1352 /* Current number of rematerialization iteration. */ 1353 int lra_rematerialization_iter; 1354 1355 /* Entry point of the rematerialization sub-pass. Return true if we 1356 did any rematerialization. */ 1357 bool 1358 lra_remat (void) 1359 { 1360 basic_block bb; 1361 bool result; 1362 int max_regno = max_reg_num (); 1363 1364 if (! flag_lra_remat) 1365 return false; 1366 lra_rematerialization_iter++; 1367 if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES) 1368 return false; 1369 if (lra_dump_file != NULL) 1370 fprintf (lra_dump_file, 1371 "\n******** Rematerialization #%d: ********\n\n", 1372 lra_rematerialization_iter); 1373 timevar_push (TV_LRA_REMAT); 1374 insn_to_cand = XCNEWVEC (cand_t, get_max_uid ()); 1375 insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ()); 1376 regno_cands = XCNEWVEC (cand_t, max_regno); 1377 all_cands.create (8000); 1378 call_used_regs_arr_len = 0; 1379 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1380 if (call_used_regs[i]) 1381 call_used_regs_arr[call_used_regs_arr_len++] = i; 1382 initiate_cand_table (); 1383 create_remat_bb_data (); 1384 bitmap_initialize (&temp_bitmap, ®_obstack); 1385 bitmap_initialize (&subreg_regs, ®_obstack); 1386 calculate_local_reg_remat_bb_data (); 1387 create_cands (); 1388 calculate_livein_cands (); 1389 calculate_gen_cands (); 1390 bitmap_initialize (&all_blocks, ®_obstack); 1391 FOR_ALL_BB_FN (bb, cfun) 1392 bitmap_set_bit (&all_blocks, bb->index); 1393 calculate_global_remat_bb_data (); 1394 dump_candidates_and_remat_bb_data (); 1395 result = do_remat (); 1396 all_cands.release (); 1397 bitmap_clear (&temp_bitmap); 1398 bitmap_clear (&subreg_regs); 1399 finish_remat_bb_data (); 1400 finish_cand_table (); 1401 bitmap_clear (&all_blocks); 1402 free (regno_cands); 1403 free (insn_to_cand); 1404 free (insn_to_cand_activation); 1405 timevar_pop (TV_LRA_REMAT); 1406 return result; 1407 } 1408