1 /* Standard problems for dataflow support routines. 2 Copyright (C) 1999-2017 Free Software Foundation, Inc. 3 Originally contributed by Michael P. Hayes 4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) 5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) 6 and Kenneth Zadeck (zadeck@naturalbridge.com). 7 8 This file is part of GCC. 9 10 GCC is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free 12 Software Foundation; either version 3, or (at your option) any later 13 version. 14 15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18 for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with GCC; see the file COPYING3. If not see 22 <http://www.gnu.org/licenses/>. */ 23 24 #include "config.h" 25 #include "system.h" 26 #include "coretypes.h" 27 #include "backend.h" 28 #include "target.h" 29 #include "rtl.h" 30 #include "df.h" 31 #include "memmodel.h" 32 #include "tm_p.h" 33 #include "insn-config.h" 34 #include "cfganal.h" 35 #include "dce.h" 36 #include "valtrack.h" 37 #include "dumpfile.h" 38 #include "rtl-iter.h" 39 40 /* Note that turning REG_DEAD_DEBUGGING on will cause 41 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints 42 addresses in the dumps. */ 43 #define REG_DEAD_DEBUGGING 0 44 45 #define DF_SPARSE_THRESHOLD 32 46 47 static bitmap_head seen_in_block; 48 static bitmap_head seen_in_insn; 49 50 /*---------------------------------------------------------------------------- 51 Utility functions. 52 ----------------------------------------------------------------------------*/ 53 54 /* Generic versions to get the void* version of the block info. Only 55 used inside the problem instance vectors. */ 56 57 /* Dump a def-use or use-def chain for REF to FILE. */ 58 59 void 60 df_chain_dump (struct df_link *link, FILE *file) 61 { 62 fprintf (file, "{ "); 63 for (; link; link = link->next) 64 { 65 fprintf (file, "%c%d(bb %d insn %d) ", 66 DF_REF_REG_DEF_P (link->ref) 67 ? 'd' 68 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u', 69 DF_REF_ID (link->ref), 70 DF_REF_BBNO (link->ref), 71 DF_REF_IS_ARTIFICIAL (link->ref) 72 ? -1 : DF_REF_INSN_UID (link->ref)); 73 } 74 fprintf (file, "}"); 75 } 76 77 78 /* Print some basic block info as part of df_dump. */ 79 80 void 81 df_print_bb_index (basic_block bb, FILE *file) 82 { 83 edge e; 84 edge_iterator ei; 85 86 fprintf (file, "\n( "); 87 FOR_EACH_EDGE (e, ei, bb->preds) 88 { 89 basic_block pred = e->src; 90 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : ""); 91 } 92 fprintf (file, ")->[%d]->( ", bb->index); 93 FOR_EACH_EDGE (e, ei, bb->succs) 94 { 95 basic_block succ = e->dest; 96 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : ""); 97 } 98 fprintf (file, ")\n"); 99 } 100 101 102 /*---------------------------------------------------------------------------- 103 REACHING DEFINITIONS 104 105 Find the locations in the function where each definition site for a 106 pseudo reaches. In and out bitvectors are built for each basic 107 block. The id field in the ref is used to index into these sets. 108 See df.h for details. 109 110 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching 111 existing uses are included in the global reaching DEFs set, or in other 112 words only DEFs that are still live. This is a kind of pruned version 113 of the traditional reaching definitions problem that is much less 114 complex to compute and produces enough information to compute UD-chains. 115 In this context, live must be interpreted in the DF_LR sense: Uses that 116 are upward exposed but maybe not initialized on all paths through the 117 CFG. For a USE that is not reached by a DEF on all paths, we still want 118 to make those DEFs that do reach the USE visible, and pruning based on 119 DF_LIVE would make that impossible. 120 ----------------------------------------------------------------------------*/ 121 122 /* This problem plays a large number of games for the sake of 123 efficiency. 124 125 1) The order of the bits in the bitvectors. After the scanning 126 phase, all of the defs are sorted. All of the defs for the reg 0 127 are first, followed by all defs for reg 1 and so on. 128 129 2) There are two kill sets, one if the number of defs is less or 130 equal to DF_SPARSE_THRESHOLD and another if the number of defs is 131 greater. 132 133 <= : Data is built directly in the kill set. 134 135 > : One level of indirection is used to keep from generating long 136 strings of 1 bits in the kill sets. Bitvectors that are indexed 137 by the regnum are used to represent that there is a killing def 138 for the register. The confluence and transfer functions use 139 these along with the bitmap_clear_range call to remove ranges of 140 bits without actually generating a knockout vector. 141 142 The kill and sparse_kill and the dense_invalidated_by_call and 143 sparse_invalidated_by_call both play this game. */ 144 145 /* Private data used to compute the solution for this problem. These 146 data structures are not accessible outside of this module. */ 147 struct df_rd_problem_data 148 { 149 /* The set of defs to regs invalidated by call. */ 150 bitmap_head sparse_invalidated_by_call; 151 /* The set of defs to regs invalidate by call for rd. */ 152 bitmap_head dense_invalidated_by_call; 153 /* An obstack for the bitmaps we need for this problem. */ 154 bitmap_obstack rd_bitmaps; 155 }; 156 157 158 /* Free basic block info. */ 159 160 static void 161 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 162 void *vbb_info) 163 { 164 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info; 165 if (bb_info) 166 { 167 bitmap_clear (&bb_info->kill); 168 bitmap_clear (&bb_info->sparse_kill); 169 bitmap_clear (&bb_info->gen); 170 bitmap_clear (&bb_info->in); 171 bitmap_clear (&bb_info->out); 172 } 173 } 174 175 176 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are 177 not touched unless the block is new. */ 178 179 static void 180 df_rd_alloc (bitmap all_blocks) 181 { 182 unsigned int bb_index; 183 bitmap_iterator bi; 184 struct df_rd_problem_data *problem_data; 185 186 if (df_rd->problem_data) 187 { 188 problem_data = (struct df_rd_problem_data *) df_rd->problem_data; 189 bitmap_clear (&problem_data->sparse_invalidated_by_call); 190 bitmap_clear (&problem_data->dense_invalidated_by_call); 191 } 192 else 193 { 194 problem_data = XNEW (struct df_rd_problem_data); 195 df_rd->problem_data = problem_data; 196 197 bitmap_obstack_initialize (&problem_data->rd_bitmaps); 198 bitmap_initialize (&problem_data->sparse_invalidated_by_call, 199 &problem_data->rd_bitmaps); 200 bitmap_initialize (&problem_data->dense_invalidated_by_call, 201 &problem_data->rd_bitmaps); 202 } 203 204 df_grow_bb_info (df_rd); 205 206 /* Because of the clustering of all use sites for the same pseudo, 207 we have to process all of the blocks before doing the analysis. */ 208 209 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 210 { 211 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 212 213 /* When bitmaps are already initialized, just clear them. */ 214 if (bb_info->kill.obstack) 215 { 216 bitmap_clear (&bb_info->kill); 217 bitmap_clear (&bb_info->sparse_kill); 218 bitmap_clear (&bb_info->gen); 219 } 220 else 221 { 222 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps); 223 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps); 224 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps); 225 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps); 226 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps); 227 } 228 } 229 df_rd->optional_p = true; 230 } 231 232 233 /* Add the effect of the top artificial defs of BB to the reaching definitions 234 bitmap LOCAL_RD. */ 235 236 void 237 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd) 238 { 239 int bb_index = bb->index; 240 df_ref def; 241 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 242 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 243 { 244 unsigned int dregno = DF_REF_REGNO (def); 245 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) 246 bitmap_clear_range (local_rd, 247 DF_DEFS_BEGIN (dregno), 248 DF_DEFS_COUNT (dregno)); 249 bitmap_set_bit (local_rd, DF_REF_ID (def)); 250 } 251 } 252 253 /* Add the effect of the defs of INSN to the reaching definitions bitmap 254 LOCAL_RD. */ 255 256 void 257 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn, 258 bitmap local_rd) 259 { 260 df_ref def; 261 262 FOR_EACH_INSN_DEF (def, insn) 263 { 264 unsigned int dregno = DF_REF_REGNO (def); 265 if ((!(df->changeable_flags & DF_NO_HARD_REGS)) 266 || (dregno >= FIRST_PSEUDO_REGISTER)) 267 { 268 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) 269 bitmap_clear_range (local_rd, 270 DF_DEFS_BEGIN (dregno), 271 DF_DEFS_COUNT (dregno)); 272 if (!(DF_REF_FLAGS (def) 273 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 274 bitmap_set_bit (local_rd, DF_REF_ID (def)); 275 } 276 } 277 } 278 279 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit 280 more complicated than just simulating, because we must produce the 281 gen and kill sets and hence deal with the two possible representations 282 of kill sets. */ 283 284 static void 285 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, 286 df_ref def, 287 int top_flag) 288 { 289 for (; def; def = DF_REF_NEXT_LOC (def)) 290 { 291 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) 292 { 293 unsigned int regno = DF_REF_REGNO (def); 294 unsigned int begin = DF_DEFS_BEGIN (regno); 295 unsigned int n_defs = DF_DEFS_COUNT (regno); 296 297 if ((!(df->changeable_flags & DF_NO_HARD_REGS)) 298 || (regno >= FIRST_PSEUDO_REGISTER)) 299 { 300 /* Only the last def(s) for a regno in the block has any 301 effect. */ 302 if (!bitmap_bit_p (&seen_in_block, regno)) 303 { 304 /* The first def for regno in insn gets to knock out the 305 defs from other instructions. */ 306 if ((!bitmap_bit_p (&seen_in_insn, regno)) 307 /* If the def is to only part of the reg, it does 308 not kill the other defs that reach here. */ 309 && (!(DF_REF_FLAGS (def) & 310 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)))) 311 { 312 if (n_defs > DF_SPARSE_THRESHOLD) 313 { 314 bitmap_set_bit (&bb_info->sparse_kill, regno); 315 bitmap_clear_range (&bb_info->gen, begin, n_defs); 316 } 317 else 318 { 319 bitmap_set_range (&bb_info->kill, begin, n_defs); 320 bitmap_clear_range (&bb_info->gen, begin, n_defs); 321 } 322 } 323 324 bitmap_set_bit (&seen_in_insn, regno); 325 /* All defs for regno in the instruction may be put into 326 the gen set. */ 327 if (!(DF_REF_FLAGS (def) 328 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 329 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def)); 330 } 331 } 332 } 333 } 334 } 335 336 /* Compute local reaching def info for basic block BB. */ 337 338 static void 339 df_rd_bb_local_compute (unsigned int bb_index) 340 { 341 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 342 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 343 rtx_insn *insn; 344 345 bitmap_clear (&seen_in_block); 346 bitmap_clear (&seen_in_insn); 347 348 /* Artificials are only hard regs. */ 349 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 350 df_rd_bb_local_compute_process_def (bb_info, 351 df_get_artificial_defs (bb_index), 352 0); 353 354 FOR_BB_INSNS_REVERSE (bb, insn) 355 { 356 unsigned int uid = INSN_UID (insn); 357 358 if (!INSN_P (insn)) 359 continue; 360 361 df_rd_bb_local_compute_process_def (bb_info, 362 DF_INSN_UID_DEFS (uid), 0); 363 364 /* This complex dance with the two bitmaps is required because 365 instructions can assign twice to the same pseudo. This 366 generally happens with calls that will have one def for the 367 result and another def for the clobber. If only one vector 368 is used and the clobber goes first, the result will be 369 lost. */ 370 bitmap_ior_into (&seen_in_block, &seen_in_insn); 371 bitmap_clear (&seen_in_insn); 372 } 373 374 /* Process the artificial defs at the top of the block last since we 375 are going backwards through the block and these are logically at 376 the start. */ 377 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 378 df_rd_bb_local_compute_process_def (bb_info, 379 df_get_artificial_defs (bb_index), 380 DF_REF_AT_TOP); 381 } 382 383 384 /* Compute local reaching def info for each basic block within BLOCKS. */ 385 386 static void 387 df_rd_local_compute (bitmap all_blocks) 388 { 389 unsigned int bb_index; 390 bitmap_iterator bi; 391 unsigned int regno; 392 struct df_rd_problem_data *problem_data 393 = (struct df_rd_problem_data *) df_rd->problem_data; 394 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call; 395 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call; 396 397 bitmap_initialize (&seen_in_block, &df_bitmap_obstack); 398 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack); 399 400 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG); 401 402 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 403 { 404 df_rd_bb_local_compute (bb_index); 405 } 406 407 /* Set up the knockout bit vectors to be applied across EH_EDGES. */ 408 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi) 409 { 410 if (! HARD_REGISTER_NUM_P (regno) 411 || !(df->changeable_flags & DF_NO_HARD_REGS)) 412 { 413 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD) 414 bitmap_set_bit (sparse_invalidated, regno); 415 else 416 bitmap_set_range (dense_invalidated, 417 DF_DEFS_BEGIN (regno), 418 DF_DEFS_COUNT (regno)); 419 } 420 } 421 422 bitmap_clear (&seen_in_block); 423 bitmap_clear (&seen_in_insn); 424 } 425 426 427 /* Initialize the solution bit vectors for problem. */ 428 429 static void 430 df_rd_init_solution (bitmap all_blocks) 431 { 432 unsigned int bb_index; 433 bitmap_iterator bi; 434 435 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 436 { 437 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 438 439 bitmap_copy (&bb_info->out, &bb_info->gen); 440 bitmap_clear (&bb_info->in); 441 } 442 } 443 444 /* In of target gets or of out of source. */ 445 446 static bool 447 df_rd_confluence_n (edge e) 448 { 449 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in; 450 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out; 451 bool changed = false; 452 453 if (e->flags & EDGE_FAKE) 454 return false; 455 456 if (e->flags & EDGE_EH) 457 { 458 struct df_rd_problem_data *problem_data 459 = (struct df_rd_problem_data *) df_rd->problem_data; 460 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call; 461 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call; 462 bitmap_iterator bi; 463 unsigned int regno; 464 bitmap_head tmp; 465 466 bitmap_initialize (&tmp, &df_bitmap_obstack); 467 bitmap_and_compl (&tmp, op2, dense_invalidated); 468 469 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi) 470 { 471 bitmap_clear_range (&tmp, 472 DF_DEFS_BEGIN (regno), 473 DF_DEFS_COUNT (regno)); 474 } 475 changed |= bitmap_ior_into (op1, &tmp); 476 bitmap_clear (&tmp); 477 return changed; 478 } 479 else 480 return bitmap_ior_into (op1, op2); 481 } 482 483 484 /* Transfer function. */ 485 486 static bool 487 df_rd_transfer_function (int bb_index) 488 { 489 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 490 unsigned int regno; 491 bitmap_iterator bi; 492 bitmap in = &bb_info->in; 493 bitmap out = &bb_info->out; 494 bitmap gen = &bb_info->gen; 495 bitmap kill = &bb_info->kill; 496 bitmap sparse_kill = &bb_info->sparse_kill; 497 bool changed = false; 498 499 if (bitmap_empty_p (sparse_kill)) 500 changed = bitmap_ior_and_compl (out, gen, in, kill); 501 else 502 { 503 struct df_rd_problem_data *problem_data; 504 bitmap_head tmp; 505 506 /* Note that TMP is _not_ a temporary bitmap if we end up replacing 507 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */ 508 problem_data = (struct df_rd_problem_data *) df_rd->problem_data; 509 bitmap_initialize (&tmp, &problem_data->rd_bitmaps); 510 511 bitmap_and_compl (&tmp, in, kill); 512 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi) 513 { 514 bitmap_clear_range (&tmp, 515 DF_DEFS_BEGIN (regno), 516 DF_DEFS_COUNT (regno)); 517 } 518 bitmap_ior_into (&tmp, gen); 519 changed = !bitmap_equal_p (&tmp, out); 520 if (changed) 521 bitmap_move (out, &tmp); 522 else 523 bitmap_clear (&tmp); 524 } 525 526 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS) 527 { 528 /* Create a mask of DEFs for all registers live at the end of this 529 basic block, and mask out DEFs of registers that are not live. 530 Computing the mask looks costly, but the benefit of the pruning 531 outweighs the cost. */ 532 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 533 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out; 534 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack); 535 unsigned int regno; 536 bitmap_iterator bi; 537 538 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi) 539 bitmap_set_range (live_defs, 540 DF_DEFS_BEGIN (regno), 541 DF_DEFS_COUNT (regno)); 542 changed |= bitmap_and_into (&bb_info->out, live_defs); 543 BITMAP_FREE (live_defs); 544 } 545 546 return changed; 547 } 548 549 /* Free all storage associated with the problem. */ 550 551 static void 552 df_rd_free (void) 553 { 554 struct df_rd_problem_data *problem_data 555 = (struct df_rd_problem_data *) df_rd->problem_data; 556 557 if (problem_data) 558 { 559 bitmap_obstack_release (&problem_data->rd_bitmaps); 560 561 df_rd->block_info_size = 0; 562 free (df_rd->block_info); 563 df_rd->block_info = NULL; 564 free (df_rd->problem_data); 565 } 566 free (df_rd); 567 } 568 569 570 /* Debugging info. */ 571 572 static void 573 df_rd_start_dump (FILE *file) 574 { 575 struct df_rd_problem_data *problem_data 576 = (struct df_rd_problem_data *) df_rd->problem_data; 577 unsigned int m = DF_REG_SIZE (df); 578 unsigned int regno; 579 580 if (!df_rd->block_info) 581 return; 582 583 fprintf (file, ";; Reaching defs:\n"); 584 585 fprintf (file, ";; sparse invalidated \t"); 586 dump_bitmap (file, &problem_data->sparse_invalidated_by_call); 587 fprintf (file, ";; dense invalidated \t"); 588 dump_bitmap (file, &problem_data->dense_invalidated_by_call); 589 590 fprintf (file, ";; reg->defs[] map:\t"); 591 for (regno = 0; regno < m; regno++) 592 if (DF_DEFS_COUNT (regno)) 593 fprintf (file, "%d[%d,%d] ", regno, 594 DF_DEFS_BEGIN (regno), 595 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1); 596 fprintf (file, "\n"); 597 } 598 599 600 static void 601 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file) 602 { 603 bitmap_head tmp; 604 unsigned int regno; 605 unsigned int m = DF_REG_SIZE (df); 606 bool first_reg = true; 607 608 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set)); 609 610 bitmap_initialize (&tmp, &df_bitmap_obstack); 611 for (regno = 0; regno < m; regno++) 612 { 613 if (HARD_REGISTER_NUM_P (regno) 614 && (df->changeable_flags & DF_NO_HARD_REGS)) 615 continue; 616 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno)); 617 bitmap_and_into (&tmp, defs_set); 618 if (! bitmap_empty_p (&tmp)) 619 { 620 bitmap_iterator bi; 621 unsigned int ix; 622 bool first_def = true; 623 624 if (! first_reg) 625 fprintf (file, ","); 626 first_reg = false; 627 628 fprintf (file, "%u[", regno); 629 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi) 630 { 631 fprintf (file, "%s%u", first_def ? "" : ",", ix); 632 first_def = false; 633 } 634 fprintf (file, "]"); 635 } 636 bitmap_clear (&tmp); 637 } 638 639 fprintf (file, "\n"); 640 bitmap_clear (&tmp); 641 } 642 643 /* Debugging info at top of bb. */ 644 645 static void 646 df_rd_top_dump (basic_block bb, FILE *file) 647 { 648 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index); 649 if (!bb_info) 650 return; 651 652 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file); 653 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file); 654 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file); 655 } 656 657 658 /* Debugging info at bottom of bb. */ 659 660 static void 661 df_rd_bottom_dump (basic_block bb, FILE *file) 662 { 663 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index); 664 if (!bb_info) 665 return; 666 667 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file); 668 } 669 670 /* All of the information associated with every instance of the problem. */ 671 672 static const struct df_problem problem_RD = 673 { 674 DF_RD, /* Problem id. */ 675 DF_FORWARD, /* Direction. */ 676 df_rd_alloc, /* Allocate the problem specific data. */ 677 NULL, /* Reset global information. */ 678 df_rd_free_bb_info, /* Free basic block info. */ 679 df_rd_local_compute, /* Local compute function. */ 680 df_rd_init_solution, /* Init the solution specific data. */ 681 df_worklist_dataflow, /* Worklist solver. */ 682 NULL, /* Confluence operator 0. */ 683 df_rd_confluence_n, /* Confluence operator n. */ 684 df_rd_transfer_function, /* Transfer function. */ 685 NULL, /* Finalize function. */ 686 df_rd_free, /* Free all of the problem information. */ 687 df_rd_free, /* Remove this problem from the stack of dataflow problems. */ 688 df_rd_start_dump, /* Debugging. */ 689 df_rd_top_dump, /* Debugging start block. */ 690 df_rd_bottom_dump, /* Debugging end block. */ 691 NULL, /* Debugging start insn. */ 692 NULL, /* Debugging end insn. */ 693 NULL, /* Incremental solution verify start. */ 694 NULL, /* Incremental solution verify end. */ 695 NULL, /* Dependent problem. */ 696 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */ 697 TV_DF_RD, /* Timing variable. */ 698 true /* Reset blocks on dropping out of blocks_to_analyze. */ 699 }; 700 701 702 703 /* Create a new RD instance and add it to the existing instance 704 of DF. */ 705 706 void 707 df_rd_add_problem (void) 708 { 709 df_add_problem (&problem_RD); 710 } 711 712 713 714 /*---------------------------------------------------------------------------- 715 LIVE REGISTERS 716 717 Find the locations in the function where any use of a pseudo can 718 reach in the backwards direction. In and out bitvectors are built 719 for each basic block. The regno is used to index into these sets. 720 See df.h for details. 721 ----------------------------------------------------------------------------*/ 722 723 /* Private data used to verify the solution for this problem. */ 724 struct df_lr_problem_data 725 { 726 bitmap_head *in; 727 bitmap_head *out; 728 /* An obstack for the bitmaps we need for this problem. */ 729 bitmap_obstack lr_bitmaps; 730 }; 731 732 /* Free basic block info. */ 733 734 static void 735 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 736 void *vbb_info) 737 { 738 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info; 739 if (bb_info) 740 { 741 bitmap_clear (&bb_info->use); 742 bitmap_clear (&bb_info->def); 743 bitmap_clear (&bb_info->in); 744 bitmap_clear (&bb_info->out); 745 } 746 } 747 748 749 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are 750 not touched unless the block is new. */ 751 752 static void 753 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 754 { 755 unsigned int bb_index; 756 bitmap_iterator bi; 757 struct df_lr_problem_data *problem_data; 758 759 df_grow_bb_info (df_lr); 760 if (df_lr->problem_data) 761 problem_data = (struct df_lr_problem_data *) df_lr->problem_data; 762 else 763 { 764 problem_data = XNEW (struct df_lr_problem_data); 765 df_lr->problem_data = problem_data; 766 767 problem_data->out = NULL; 768 problem_data->in = NULL; 769 bitmap_obstack_initialize (&problem_data->lr_bitmaps); 770 } 771 772 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi) 773 { 774 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); 775 776 /* When bitmaps are already initialized, just clear them. */ 777 if (bb_info->use.obstack) 778 { 779 bitmap_clear (&bb_info->def); 780 bitmap_clear (&bb_info->use); 781 } 782 else 783 { 784 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps); 785 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps); 786 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps); 787 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps); 788 } 789 } 790 791 df_lr->optional_p = false; 792 } 793 794 795 /* Reset the global solution for recalculation. */ 796 797 static void 798 df_lr_reset (bitmap all_blocks) 799 { 800 unsigned int bb_index; 801 bitmap_iterator bi; 802 803 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 804 { 805 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); 806 gcc_assert (bb_info); 807 bitmap_clear (&bb_info->in); 808 bitmap_clear (&bb_info->out); 809 } 810 } 811 812 813 /* Compute local live register info for basic block BB. */ 814 815 static void 816 df_lr_bb_local_compute (unsigned int bb_index) 817 { 818 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 819 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); 820 rtx_insn *insn; 821 df_ref def, use; 822 823 /* Process the registers set in an exception handler. */ 824 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 825 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 826 { 827 unsigned int dregno = DF_REF_REGNO (def); 828 bitmap_set_bit (&bb_info->def, dregno); 829 bitmap_clear_bit (&bb_info->use, dregno); 830 } 831 832 /* Process the hardware registers that are always live. */ 833 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 834 /* Add use to set of uses in this BB. */ 835 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) 836 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use)); 837 838 FOR_BB_INSNS_REVERSE (bb, insn) 839 { 840 if (!NONDEBUG_INSN_P (insn)) 841 continue; 842 843 df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 844 FOR_EACH_INSN_INFO_DEF (def, insn_info) 845 /* If the def is to only part of the reg, it does 846 not kill the other defs that reach here. */ 847 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) 848 { 849 unsigned int dregno = DF_REF_REGNO (def); 850 bitmap_set_bit (&bb_info->def, dregno); 851 bitmap_clear_bit (&bb_info->use, dregno); 852 } 853 854 FOR_EACH_INSN_INFO_USE (use, insn_info) 855 /* Add use to set of uses in this BB. */ 856 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use)); 857 } 858 859 /* Process the registers set in an exception handler or the hard 860 frame pointer if this block is the target of a non local 861 goto. */ 862 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 863 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 864 { 865 unsigned int dregno = DF_REF_REGNO (def); 866 bitmap_set_bit (&bb_info->def, dregno); 867 bitmap_clear_bit (&bb_info->use, dregno); 868 } 869 870 #ifdef EH_USES 871 /* Process the uses that are live into an exception handler. */ 872 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 873 /* Add use to set of uses in this BB. */ 874 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) 875 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use)); 876 #endif 877 878 /* If the df_live problem is not defined, such as at -O0 and -O1, we 879 still need to keep the luids up to date. This is normally done 880 in the df_live problem since this problem has a forwards 881 scan. */ 882 if (!df_live) 883 df_recompute_luids (bb); 884 } 885 886 887 /* Compute local live register info for each basic block within BLOCKS. */ 888 889 static void 890 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) 891 { 892 unsigned int bb_index, i; 893 bitmap_iterator bi; 894 895 bitmap_clear (&df->hardware_regs_used); 896 897 /* The all-important stack pointer must always be live. */ 898 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM); 899 900 /* Global regs are always live, too. */ 901 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 902 if (global_regs[i]) 903 bitmap_set_bit (&df->hardware_regs_used, i); 904 905 /* Before reload, there are a few registers that must be forced 906 live everywhere -- which might not already be the case for 907 blocks within infinite loops. */ 908 if (!reload_completed) 909 { 910 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM; 911 /* Any reference to any pseudo before reload is a potential 912 reference of the frame pointer. */ 913 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM); 914 915 /* Pseudos with argument area equivalences may require 916 reloading via the argument pointer. */ 917 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 918 && fixed_regs[ARG_POINTER_REGNUM]) 919 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM); 920 921 /* Any constant, or pseudo with constant equivalences, may 922 require reloading from memory using the pic register. */ 923 if (pic_offset_table_regnum != INVALID_REGNUM 924 && fixed_regs[pic_offset_table_regnum]) 925 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum); 926 } 927 928 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi) 929 { 930 if (bb_index == EXIT_BLOCK) 931 { 932 /* The exit block is special for this problem and its bits are 933 computed from thin air. */ 934 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK); 935 bitmap_copy (&bb_info->use, df->exit_block_uses); 936 } 937 else 938 df_lr_bb_local_compute (bb_index); 939 } 940 941 bitmap_clear (df_lr->out_of_date_transfer_functions); 942 } 943 944 945 /* Initialize the solution vectors. */ 946 947 static void 948 df_lr_init (bitmap all_blocks) 949 { 950 unsigned int bb_index; 951 bitmap_iterator bi; 952 953 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 954 { 955 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); 956 bitmap_copy (&bb_info->in, &bb_info->use); 957 bitmap_clear (&bb_info->out); 958 } 959 } 960 961 962 /* Confluence function that processes infinite loops. This might be a 963 noreturn function that throws. And even if it isn't, getting the 964 unwind info right helps debugging. */ 965 static void 966 df_lr_confluence_0 (basic_block bb) 967 { 968 bitmap op1 = &df_lr_get_bb_info (bb->index)->out; 969 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 970 bitmap_copy (op1, &df->hardware_regs_used); 971 } 972 973 974 /* Confluence function that ignores fake edges. */ 975 976 static bool 977 df_lr_confluence_n (edge e) 978 { 979 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out; 980 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in; 981 bool changed = false; 982 983 /* Call-clobbered registers die across exception and call edges. */ 984 /* ??? Abnormal call edges ignored for the moment, as this gets 985 confused by sibling call edges, which crashes reg-stack. */ 986 if (e->flags & EDGE_EH) 987 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); 988 else 989 changed = bitmap_ior_into (op1, op2); 990 991 changed |= bitmap_ior_into (op1, &df->hardware_regs_used); 992 return changed; 993 } 994 995 996 /* Transfer function. */ 997 998 static bool 999 df_lr_transfer_function (int bb_index) 1000 { 1001 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index); 1002 bitmap in = &bb_info->in; 1003 bitmap out = &bb_info->out; 1004 bitmap use = &bb_info->use; 1005 bitmap def = &bb_info->def; 1006 1007 return bitmap_ior_and_compl (in, use, out, def); 1008 } 1009 1010 1011 /* Run the fast dce as a side effect of building LR. */ 1012 1013 static void 1014 df_lr_finalize (bitmap all_blocks) 1015 { 1016 df_lr->solutions_dirty = false; 1017 if (df->changeable_flags & DF_LR_RUN_DCE) 1018 { 1019 run_fast_df_dce (); 1020 1021 /* If dce deletes some instructions, we need to recompute the lr 1022 solution before proceeding further. The problem is that fast 1023 dce is a pessimestic dataflow algorithm. In the case where 1024 it deletes a statement S inside of a loop, the uses inside of 1025 S may not be deleted from the dataflow solution because they 1026 were carried around the loop. While it is conservatively 1027 correct to leave these extra bits, the standards of df 1028 require that we maintain the best possible (least fixed 1029 point) solution. The only way to do that is to redo the 1030 iteration from the beginning. See PR35805 for an 1031 example. */ 1032 if (df_lr->solutions_dirty) 1033 { 1034 df_clear_flags (DF_LR_RUN_DCE); 1035 df_lr_alloc (all_blocks); 1036 df_lr_local_compute (all_blocks); 1037 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks); 1038 df_lr_finalize (all_blocks); 1039 df_set_flags (DF_LR_RUN_DCE); 1040 } 1041 } 1042 } 1043 1044 1045 /* Free all storage associated with the problem. */ 1046 1047 static void 1048 df_lr_free (void) 1049 { 1050 struct df_lr_problem_data *problem_data 1051 = (struct df_lr_problem_data *) df_lr->problem_data; 1052 if (df_lr->block_info) 1053 { 1054 1055 df_lr->block_info_size = 0; 1056 free (df_lr->block_info); 1057 df_lr->block_info = NULL; 1058 bitmap_obstack_release (&problem_data->lr_bitmaps); 1059 free (df_lr->problem_data); 1060 df_lr->problem_data = NULL; 1061 } 1062 1063 BITMAP_FREE (df_lr->out_of_date_transfer_functions); 1064 free (df_lr); 1065 } 1066 1067 1068 /* Debugging info at top of bb. */ 1069 1070 static void 1071 df_lr_top_dump (basic_block bb, FILE *file) 1072 { 1073 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); 1074 struct df_lr_problem_data *problem_data; 1075 if (!bb_info) 1076 return; 1077 1078 fprintf (file, ";; lr in \t"); 1079 df_print_regset (file, &bb_info->in); 1080 if (df_lr->problem_data) 1081 { 1082 problem_data = (struct df_lr_problem_data *)df_lr->problem_data; 1083 if (problem_data->in) 1084 { 1085 fprintf (file, ";; old in \t"); 1086 df_print_regset (file, &problem_data->in[bb->index]); 1087 } 1088 } 1089 fprintf (file, ";; lr use \t"); 1090 df_print_regset (file, &bb_info->use); 1091 fprintf (file, ";; lr def \t"); 1092 df_print_regset (file, &bb_info->def); 1093 } 1094 1095 1096 /* Debugging info at bottom of bb. */ 1097 1098 static void 1099 df_lr_bottom_dump (basic_block bb, FILE *file) 1100 { 1101 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); 1102 struct df_lr_problem_data *problem_data; 1103 if (!bb_info) 1104 return; 1105 1106 fprintf (file, ";; lr out \t"); 1107 df_print_regset (file, &bb_info->out); 1108 if (df_lr->problem_data) 1109 { 1110 problem_data = (struct df_lr_problem_data *)df_lr->problem_data; 1111 if (problem_data->out) 1112 { 1113 fprintf (file, ";; old out \t"); 1114 df_print_regset (file, &problem_data->out[bb->index]); 1115 } 1116 } 1117 } 1118 1119 1120 /* Build the datastructure to verify that the solution to the dataflow 1121 equations is not dirty. */ 1122 1123 static void 1124 df_lr_verify_solution_start (void) 1125 { 1126 basic_block bb; 1127 struct df_lr_problem_data *problem_data; 1128 if (df_lr->solutions_dirty) 1129 return; 1130 1131 /* Set it true so that the solution is recomputed. */ 1132 df_lr->solutions_dirty = true; 1133 1134 problem_data = (struct df_lr_problem_data *)df_lr->problem_data; 1135 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 1136 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 1137 1138 FOR_ALL_BB_FN (bb, cfun) 1139 { 1140 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps); 1141 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps); 1142 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb)); 1143 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb)); 1144 } 1145 } 1146 1147 1148 /* Compare the saved datastructure and the new solution to the dataflow 1149 equations. */ 1150 1151 static void 1152 df_lr_verify_solution_end (void) 1153 { 1154 struct df_lr_problem_data *problem_data; 1155 basic_block bb; 1156 1157 problem_data = (struct df_lr_problem_data *)df_lr->problem_data; 1158 1159 if (!problem_data->out) 1160 return; 1161 1162 if (df_lr->solutions_dirty) 1163 /* Do not check if the solution is still dirty. See the comment 1164 in df_lr_finalize for details. */ 1165 df_lr->solutions_dirty = false; 1166 else 1167 FOR_ALL_BB_FN (bb, cfun) 1168 { 1169 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb))) 1170 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb)))) 1171 { 1172 /*df_dump (stderr);*/ 1173 gcc_unreachable (); 1174 } 1175 } 1176 1177 /* Cannot delete them immediately because you may want to dump them 1178 if the comparison fails. */ 1179 FOR_ALL_BB_FN (bb, cfun) 1180 { 1181 bitmap_clear (&problem_data->in[bb->index]); 1182 bitmap_clear (&problem_data->out[bb->index]); 1183 } 1184 1185 free (problem_data->in); 1186 free (problem_data->out); 1187 problem_data->in = NULL; 1188 problem_data->out = NULL; 1189 } 1190 1191 1192 /* All of the information associated with every instance of the problem. */ 1193 1194 static const struct df_problem problem_LR = 1195 { 1196 DF_LR, /* Problem id. */ 1197 DF_BACKWARD, /* Direction. */ 1198 df_lr_alloc, /* Allocate the problem specific data. */ 1199 df_lr_reset, /* Reset global information. */ 1200 df_lr_free_bb_info, /* Free basic block info. */ 1201 df_lr_local_compute, /* Local compute function. */ 1202 df_lr_init, /* Init the solution specific data. */ 1203 df_worklist_dataflow, /* Worklist solver. */ 1204 df_lr_confluence_0, /* Confluence operator 0. */ 1205 df_lr_confluence_n, /* Confluence operator n. */ 1206 df_lr_transfer_function, /* Transfer function. */ 1207 df_lr_finalize, /* Finalize function. */ 1208 df_lr_free, /* Free all of the problem information. */ 1209 NULL, /* Remove this problem from the stack of dataflow problems. */ 1210 NULL, /* Debugging. */ 1211 df_lr_top_dump, /* Debugging start block. */ 1212 df_lr_bottom_dump, /* Debugging end block. */ 1213 NULL, /* Debugging start insn. */ 1214 NULL, /* Debugging end insn. */ 1215 df_lr_verify_solution_start,/* Incremental solution verify start. */ 1216 df_lr_verify_solution_end, /* Incremental solution verify end. */ 1217 NULL, /* Dependent problem. */ 1218 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */ 1219 TV_DF_LR, /* Timing variable. */ 1220 false /* Reset blocks on dropping out of blocks_to_analyze. */ 1221 }; 1222 1223 1224 /* Create a new DATAFLOW instance and add it to an existing instance 1225 of DF. The returned structure is what is used to get at the 1226 solution. */ 1227 1228 void 1229 df_lr_add_problem (void) 1230 { 1231 df_add_problem (&problem_LR); 1232 /* These will be initialized when df_scan_blocks processes each 1233 block. */ 1234 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack); 1235 } 1236 1237 1238 /* Verify that all of the lr related info is consistent and 1239 correct. */ 1240 1241 void 1242 df_lr_verify_transfer_functions (void) 1243 { 1244 basic_block bb; 1245 bitmap_head saved_def; 1246 bitmap_head saved_use; 1247 bitmap_head all_blocks; 1248 1249 if (!df) 1250 return; 1251 1252 bitmap_initialize (&saved_def, &bitmap_default_obstack); 1253 bitmap_initialize (&saved_use, &bitmap_default_obstack); 1254 bitmap_initialize (&all_blocks, &bitmap_default_obstack); 1255 1256 FOR_ALL_BB_FN (bb, cfun) 1257 { 1258 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index); 1259 bitmap_set_bit (&all_blocks, bb->index); 1260 1261 if (bb_info) 1262 { 1263 /* Make a copy of the transfer functions and then compute 1264 new ones to see if the transfer functions have 1265 changed. */ 1266 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions, 1267 bb->index)) 1268 { 1269 bitmap_copy (&saved_def, &bb_info->def); 1270 bitmap_copy (&saved_use, &bb_info->use); 1271 bitmap_clear (&bb_info->def); 1272 bitmap_clear (&bb_info->use); 1273 1274 df_lr_bb_local_compute (bb->index); 1275 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def)); 1276 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use)); 1277 } 1278 } 1279 else 1280 { 1281 /* If we do not have basic block info, the block must be in 1282 the list of dirty blocks or else some one has added a 1283 block behind our backs. */ 1284 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions, 1285 bb->index)); 1286 } 1287 /* Make sure no one created a block without following 1288 procedures. */ 1289 gcc_assert (df_scan_get_bb_info (bb->index)); 1290 } 1291 1292 /* Make sure there are no dirty bits in blocks that have been deleted. */ 1293 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions, 1294 &all_blocks)); 1295 1296 bitmap_clear (&saved_def); 1297 bitmap_clear (&saved_use); 1298 bitmap_clear (&all_blocks); 1299 } 1300 1301 1302 1303 /*---------------------------------------------------------------------------- 1304 LIVE AND MAY-INITIALIZED REGISTERS. 1305 1306 This problem first computes the IN and OUT bitvectors for the 1307 may-initialized registers problems, which is a forward problem. 1308 It gives the set of registers for which we MAY have an available 1309 definition, i.e. for which there is an available definition on 1310 at least one path from the entry block to the entry/exit of a 1311 basic block. Sets generate a definition, while clobbers kill 1312 a definition. 1313 1314 In and out bitvectors are built for each basic block and are indexed by 1315 regnum (see df.h for details). In and out bitvectors in struct 1316 df_live_bb_info actually refers to the may-initialized problem; 1317 1318 Then, the in and out sets for the LIVE problem itself are computed. 1319 These are the logical AND of the IN and OUT sets from the LR problem 1320 and the may-initialized problem. 1321 ----------------------------------------------------------------------------*/ 1322 1323 /* Private data used to verify the solution for this problem. */ 1324 struct df_live_problem_data 1325 { 1326 bitmap_head *in; 1327 bitmap_head *out; 1328 /* An obstack for the bitmaps we need for this problem. */ 1329 bitmap_obstack live_bitmaps; 1330 }; 1331 1332 /* Scratch var used by transfer functions. This is used to implement 1333 an optimization to reduce the amount of space used to compute the 1334 combined lr and live analysis. */ 1335 static bitmap_head df_live_scratch; 1336 1337 1338 /* Free basic block info. */ 1339 1340 static void 1341 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 1342 void *vbb_info) 1343 { 1344 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info; 1345 if (bb_info) 1346 { 1347 bitmap_clear (&bb_info->gen); 1348 bitmap_clear (&bb_info->kill); 1349 bitmap_clear (&bb_info->in); 1350 bitmap_clear (&bb_info->out); 1351 } 1352 } 1353 1354 1355 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are 1356 not touched unless the block is new. */ 1357 1358 static void 1359 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 1360 { 1361 unsigned int bb_index; 1362 bitmap_iterator bi; 1363 struct df_live_problem_data *problem_data; 1364 1365 if (df_live->problem_data) 1366 problem_data = (struct df_live_problem_data *) df_live->problem_data; 1367 else 1368 { 1369 problem_data = XNEW (struct df_live_problem_data); 1370 df_live->problem_data = problem_data; 1371 1372 problem_data->out = NULL; 1373 problem_data->in = NULL; 1374 bitmap_obstack_initialize (&problem_data->live_bitmaps); 1375 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps); 1376 } 1377 1378 df_grow_bb_info (df_live); 1379 1380 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi) 1381 { 1382 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); 1383 1384 /* When bitmaps are already initialized, just clear them. */ 1385 if (bb_info->kill.obstack) 1386 { 1387 bitmap_clear (&bb_info->kill); 1388 bitmap_clear (&bb_info->gen); 1389 } 1390 else 1391 { 1392 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps); 1393 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps); 1394 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps); 1395 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps); 1396 } 1397 } 1398 df_live->optional_p = (optimize <= 1); 1399 } 1400 1401 1402 /* Reset the global solution for recalculation. */ 1403 1404 static void 1405 df_live_reset (bitmap all_blocks) 1406 { 1407 unsigned int bb_index; 1408 bitmap_iterator bi; 1409 1410 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1411 { 1412 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); 1413 gcc_assert (bb_info); 1414 bitmap_clear (&bb_info->in); 1415 bitmap_clear (&bb_info->out); 1416 } 1417 } 1418 1419 1420 /* Compute local uninitialized register info for basic block BB. */ 1421 1422 static void 1423 df_live_bb_local_compute (unsigned int bb_index) 1424 { 1425 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1426 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); 1427 rtx_insn *insn; 1428 df_ref def; 1429 int luid = 0; 1430 1431 FOR_BB_INSNS (bb, insn) 1432 { 1433 unsigned int uid = INSN_UID (insn); 1434 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid); 1435 1436 /* Inserting labels does not always trigger the incremental 1437 rescanning. */ 1438 if (!insn_info) 1439 { 1440 gcc_assert (!INSN_P (insn)); 1441 insn_info = df_insn_create_insn_record (insn); 1442 } 1443 1444 DF_INSN_INFO_LUID (insn_info) = luid; 1445 if (!INSN_P (insn)) 1446 continue; 1447 1448 luid++; 1449 FOR_EACH_INSN_INFO_DEF (def, insn_info) 1450 { 1451 unsigned int regno = DF_REF_REGNO (def); 1452 1453 if (DF_REF_FLAGS_IS_SET (def, 1454 DF_REF_PARTIAL | DF_REF_CONDITIONAL)) 1455 /* All partial or conditional def 1456 seen are included in the gen set. */ 1457 bitmap_set_bit (&bb_info->gen, regno); 1458 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER)) 1459 /* Only must clobbers for the entire reg destroy the 1460 value. */ 1461 bitmap_set_bit (&bb_info->kill, regno); 1462 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) 1463 bitmap_set_bit (&bb_info->gen, regno); 1464 } 1465 } 1466 1467 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 1468 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def)); 1469 } 1470 1471 1472 /* Compute local uninitialized register info. */ 1473 1474 static void 1475 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) 1476 { 1477 unsigned int bb_index; 1478 bitmap_iterator bi; 1479 1480 df_grow_insn_info (); 1481 1482 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 1483 0, bb_index, bi) 1484 { 1485 df_live_bb_local_compute (bb_index); 1486 } 1487 1488 bitmap_clear (df_live->out_of_date_transfer_functions); 1489 } 1490 1491 1492 /* Initialize the solution vectors. */ 1493 1494 static void 1495 df_live_init (bitmap all_blocks) 1496 { 1497 unsigned int bb_index; 1498 bitmap_iterator bi; 1499 1500 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1501 { 1502 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); 1503 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); 1504 1505 /* No register may reach a location where it is not used. Thus 1506 we trim the rr result to the places where it is used. */ 1507 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out); 1508 bitmap_clear (&bb_info->in); 1509 } 1510 } 1511 1512 /* Forward confluence function that ignores fake edges. */ 1513 1514 static bool 1515 df_live_confluence_n (edge e) 1516 { 1517 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in; 1518 bitmap op2 = &df_live_get_bb_info (e->src->index)->out; 1519 1520 if (e->flags & EDGE_FAKE) 1521 return false; 1522 1523 return bitmap_ior_into (op1, op2); 1524 } 1525 1526 1527 /* Transfer function for the forwards may-initialized problem. */ 1528 1529 static bool 1530 df_live_transfer_function (int bb_index) 1531 { 1532 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index); 1533 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); 1534 bitmap in = &bb_info->in; 1535 bitmap out = &bb_info->out; 1536 bitmap gen = &bb_info->gen; 1537 bitmap kill = &bb_info->kill; 1538 1539 /* We need to use a scratch set here so that the value returned from this 1540 function invocation properly reflects whether the sets changed in a 1541 significant way; i.e. not just because the lr set was anded in. */ 1542 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out); 1543 /* No register may reach a location where it is not used. Thus 1544 we trim the rr result to the places where it is used. */ 1545 bitmap_and_into (in, &bb_lr_info->in); 1546 1547 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill); 1548 } 1549 1550 1551 /* And the LR info with the may-initialized registers to produce the LIVE info. */ 1552 1553 static void 1554 df_live_finalize (bitmap all_blocks) 1555 { 1556 1557 if (df_live->solutions_dirty) 1558 { 1559 bitmap_iterator bi; 1560 unsigned int bb_index; 1561 1562 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1563 { 1564 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index); 1565 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index); 1566 1567 /* No register may reach a location where it is not used. Thus 1568 we trim the rr result to the places where it is used. */ 1569 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in); 1570 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out); 1571 } 1572 1573 df_live->solutions_dirty = false; 1574 } 1575 } 1576 1577 1578 /* Free all storage associated with the problem. */ 1579 1580 static void 1581 df_live_free (void) 1582 { 1583 struct df_live_problem_data *problem_data 1584 = (struct df_live_problem_data *) df_live->problem_data; 1585 if (df_live->block_info) 1586 { 1587 df_live->block_info_size = 0; 1588 free (df_live->block_info); 1589 df_live->block_info = NULL; 1590 bitmap_clear (&df_live_scratch); 1591 bitmap_obstack_release (&problem_data->live_bitmaps); 1592 free (problem_data); 1593 df_live->problem_data = NULL; 1594 } 1595 BITMAP_FREE (df_live->out_of_date_transfer_functions); 1596 free (df_live); 1597 } 1598 1599 1600 /* Debugging info at top of bb. */ 1601 1602 static void 1603 df_live_top_dump (basic_block bb, FILE *file) 1604 { 1605 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); 1606 struct df_live_problem_data *problem_data; 1607 1608 if (!bb_info) 1609 return; 1610 1611 fprintf (file, ";; live in \t"); 1612 df_print_regset (file, &bb_info->in); 1613 if (df_live->problem_data) 1614 { 1615 problem_data = (struct df_live_problem_data *)df_live->problem_data; 1616 if (problem_data->in) 1617 { 1618 fprintf (file, ";; old in \t"); 1619 df_print_regset (file, &problem_data->in[bb->index]); 1620 } 1621 } 1622 fprintf (file, ";; live gen \t"); 1623 df_print_regset (file, &bb_info->gen); 1624 fprintf (file, ";; live kill\t"); 1625 df_print_regset (file, &bb_info->kill); 1626 } 1627 1628 1629 /* Debugging info at bottom of bb. */ 1630 1631 static void 1632 df_live_bottom_dump (basic_block bb, FILE *file) 1633 { 1634 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); 1635 struct df_live_problem_data *problem_data; 1636 1637 if (!bb_info) 1638 return; 1639 1640 fprintf (file, ";; live out \t"); 1641 df_print_regset (file, &bb_info->out); 1642 if (df_live->problem_data) 1643 { 1644 problem_data = (struct df_live_problem_data *)df_live->problem_data; 1645 if (problem_data->out) 1646 { 1647 fprintf (file, ";; old out \t"); 1648 df_print_regset (file, &problem_data->out[bb->index]); 1649 } 1650 } 1651 } 1652 1653 1654 /* Build the datastructure to verify that the solution to the dataflow 1655 equations is not dirty. */ 1656 1657 static void 1658 df_live_verify_solution_start (void) 1659 { 1660 basic_block bb; 1661 struct df_live_problem_data *problem_data; 1662 if (df_live->solutions_dirty) 1663 return; 1664 1665 /* Set it true so that the solution is recomputed. */ 1666 df_live->solutions_dirty = true; 1667 1668 problem_data = (struct df_live_problem_data *)df_live->problem_data; 1669 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 1670 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 1671 1672 FOR_ALL_BB_FN (bb, cfun) 1673 { 1674 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps); 1675 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps); 1676 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb)); 1677 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb)); 1678 } 1679 } 1680 1681 1682 /* Compare the saved datastructure and the new solution to the dataflow 1683 equations. */ 1684 1685 static void 1686 df_live_verify_solution_end (void) 1687 { 1688 struct df_live_problem_data *problem_data; 1689 basic_block bb; 1690 1691 problem_data = (struct df_live_problem_data *)df_live->problem_data; 1692 if (!problem_data->out) 1693 return; 1694 1695 FOR_ALL_BB_FN (bb, cfun) 1696 { 1697 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb))) 1698 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb)))) 1699 { 1700 /*df_dump (stderr);*/ 1701 gcc_unreachable (); 1702 } 1703 } 1704 1705 /* Cannot delete them immediately because you may want to dump them 1706 if the comparison fails. */ 1707 FOR_ALL_BB_FN (bb, cfun) 1708 { 1709 bitmap_clear (&problem_data->in[bb->index]); 1710 bitmap_clear (&problem_data->out[bb->index]); 1711 } 1712 1713 free (problem_data->in); 1714 free (problem_data->out); 1715 free (problem_data); 1716 df_live->problem_data = NULL; 1717 } 1718 1719 1720 /* All of the information associated with every instance of the problem. */ 1721 1722 static const struct df_problem problem_LIVE = 1723 { 1724 DF_LIVE, /* Problem id. */ 1725 DF_FORWARD, /* Direction. */ 1726 df_live_alloc, /* Allocate the problem specific data. */ 1727 df_live_reset, /* Reset global information. */ 1728 df_live_free_bb_info, /* Free basic block info. */ 1729 df_live_local_compute, /* Local compute function. */ 1730 df_live_init, /* Init the solution specific data. */ 1731 df_worklist_dataflow, /* Worklist solver. */ 1732 NULL, /* Confluence operator 0. */ 1733 df_live_confluence_n, /* Confluence operator n. */ 1734 df_live_transfer_function, /* Transfer function. */ 1735 df_live_finalize, /* Finalize function. */ 1736 df_live_free, /* Free all of the problem information. */ 1737 df_live_free, /* Remove this problem from the stack of dataflow problems. */ 1738 NULL, /* Debugging. */ 1739 df_live_top_dump, /* Debugging start block. */ 1740 df_live_bottom_dump, /* Debugging end block. */ 1741 NULL, /* Debugging start insn. */ 1742 NULL, /* Debugging end insn. */ 1743 df_live_verify_solution_start,/* Incremental solution verify start. */ 1744 df_live_verify_solution_end, /* Incremental solution verify end. */ 1745 &problem_LR, /* Dependent problem. */ 1746 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */ 1747 TV_DF_LIVE, /* Timing variable. */ 1748 false /* Reset blocks on dropping out of blocks_to_analyze. */ 1749 }; 1750 1751 1752 /* Create a new DATAFLOW instance and add it to an existing instance 1753 of DF. The returned structure is what is used to get at the 1754 solution. */ 1755 1756 void 1757 df_live_add_problem (void) 1758 { 1759 df_add_problem (&problem_LIVE); 1760 /* These will be initialized when df_scan_blocks processes each 1761 block. */ 1762 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack); 1763 } 1764 1765 1766 /* Set all of the blocks as dirty. This needs to be done if this 1767 problem is added after all of the insns have been scanned. */ 1768 1769 void 1770 df_live_set_all_dirty (void) 1771 { 1772 basic_block bb; 1773 FOR_ALL_BB_FN (bb, cfun) 1774 bitmap_set_bit (df_live->out_of_date_transfer_functions, 1775 bb->index); 1776 } 1777 1778 1779 /* Verify that all of the lr related info is consistent and 1780 correct. */ 1781 1782 void 1783 df_live_verify_transfer_functions (void) 1784 { 1785 basic_block bb; 1786 bitmap_head saved_gen; 1787 bitmap_head saved_kill; 1788 bitmap_head all_blocks; 1789 1790 if (!df) 1791 return; 1792 1793 bitmap_initialize (&saved_gen, &bitmap_default_obstack); 1794 bitmap_initialize (&saved_kill, &bitmap_default_obstack); 1795 bitmap_initialize (&all_blocks, &bitmap_default_obstack); 1796 1797 df_grow_insn_info (); 1798 1799 FOR_ALL_BB_FN (bb, cfun) 1800 { 1801 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index); 1802 bitmap_set_bit (&all_blocks, bb->index); 1803 1804 if (bb_info) 1805 { 1806 /* Make a copy of the transfer functions and then compute 1807 new ones to see if the transfer functions have 1808 changed. */ 1809 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions, 1810 bb->index)) 1811 { 1812 bitmap_copy (&saved_gen, &bb_info->gen); 1813 bitmap_copy (&saved_kill, &bb_info->kill); 1814 bitmap_clear (&bb_info->gen); 1815 bitmap_clear (&bb_info->kill); 1816 1817 df_live_bb_local_compute (bb->index); 1818 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen)); 1819 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill)); 1820 } 1821 } 1822 else 1823 { 1824 /* If we do not have basic block info, the block must be in 1825 the list of dirty blocks or else some one has added a 1826 block behind our backs. */ 1827 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions, 1828 bb->index)); 1829 } 1830 /* Make sure no one created a block without following 1831 procedures. */ 1832 gcc_assert (df_scan_get_bb_info (bb->index)); 1833 } 1834 1835 /* Make sure there are no dirty bits in blocks that have been deleted. */ 1836 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions, 1837 &all_blocks)); 1838 bitmap_clear (&saved_gen); 1839 bitmap_clear (&saved_kill); 1840 bitmap_clear (&all_blocks); 1841 } 1842 1843 /*---------------------------------------------------------------------------- 1844 MUST-INITIALIZED REGISTERS. 1845 ----------------------------------------------------------------------------*/ 1846 1847 /* Private data used to verify the solution for this problem. */ 1848 struct df_mir_problem_data 1849 { 1850 bitmap_head *in; 1851 bitmap_head *out; 1852 /* An obstack for the bitmaps we need for this problem. */ 1853 bitmap_obstack mir_bitmaps; 1854 }; 1855 1856 1857 /* Free basic block info. */ 1858 1859 static void 1860 df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 1861 void *vbb_info) 1862 { 1863 struct df_mir_bb_info *bb_info = (struct df_mir_bb_info *) vbb_info; 1864 if (bb_info) 1865 { 1866 bitmap_clear (&bb_info->gen); 1867 bitmap_clear (&bb_info->kill); 1868 bitmap_clear (&bb_info->in); 1869 bitmap_clear (&bb_info->out); 1870 } 1871 } 1872 1873 1874 /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are 1875 not touched unless the block is new. */ 1876 1877 static void 1878 df_mir_alloc (bitmap all_blocks) 1879 { 1880 unsigned int bb_index; 1881 bitmap_iterator bi; 1882 struct df_mir_problem_data *problem_data; 1883 1884 if (df_mir->problem_data) 1885 problem_data = (struct df_mir_problem_data *) df_mir->problem_data; 1886 else 1887 { 1888 problem_data = XNEW (struct df_mir_problem_data); 1889 df_mir->problem_data = problem_data; 1890 1891 problem_data->out = NULL; 1892 problem_data->in = NULL; 1893 bitmap_obstack_initialize (&problem_data->mir_bitmaps); 1894 } 1895 1896 df_grow_bb_info (df_mir); 1897 1898 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1899 { 1900 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index); 1901 1902 /* When bitmaps are already initialized, just clear them. */ 1903 if (bb_info->kill.obstack) 1904 { 1905 bitmap_clear (&bb_info->kill); 1906 bitmap_clear (&bb_info->gen); 1907 } 1908 else 1909 { 1910 bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps); 1911 bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps); 1912 bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps); 1913 bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps); 1914 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df)); 1915 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df)); 1916 } 1917 } 1918 1919 df_mir->optional_p = 1; 1920 } 1921 1922 1923 /* Reset the global solution for recalculation. */ 1924 1925 static void 1926 df_mir_reset (bitmap all_blocks) 1927 { 1928 unsigned int bb_index; 1929 bitmap_iterator bi; 1930 1931 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1932 { 1933 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index); 1934 1935 gcc_assert (bb_info); 1936 1937 bitmap_clear (&bb_info->in); 1938 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df)); 1939 bitmap_clear (&bb_info->out); 1940 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df)); 1941 } 1942 } 1943 1944 1945 /* Compute local uninitialized register info for basic block BB. */ 1946 1947 static void 1948 df_mir_bb_local_compute (unsigned int bb_index) 1949 { 1950 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1951 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index); 1952 rtx_insn *insn; 1953 int luid = 0; 1954 1955 /* Ignoring artificial defs is intentional: these often pretend that some 1956 registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even 1957 though they are not used for that. As a result, conservatively assume 1958 they may be uninitialized. */ 1959 1960 FOR_BB_INSNS (bb, insn) 1961 { 1962 unsigned int uid = INSN_UID (insn); 1963 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid); 1964 1965 /* Inserting labels does not always trigger the incremental 1966 rescanning. */ 1967 if (!insn_info) 1968 { 1969 gcc_assert (!INSN_P (insn)); 1970 insn_info = df_insn_create_insn_record (insn); 1971 } 1972 1973 DF_INSN_INFO_LUID (insn_info) = luid; 1974 if (!INSN_P (insn)) 1975 continue; 1976 1977 luid++; 1978 df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen); 1979 } 1980 } 1981 1982 1983 /* Compute local uninitialized register info. */ 1984 1985 static void 1986 df_mir_local_compute (bitmap all_blocks) 1987 { 1988 unsigned int bb_index; 1989 bitmap_iterator bi; 1990 1991 df_grow_insn_info (); 1992 1993 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1994 { 1995 df_mir_bb_local_compute (bb_index); 1996 } 1997 } 1998 1999 2000 /* Initialize the solution vectors. */ 2001 2002 static void 2003 df_mir_init (bitmap all_blocks) 2004 { 2005 df_mir_reset (all_blocks); 2006 } 2007 2008 2009 /* Initialize IN sets for blocks with no predecessors: when landing on such 2010 blocks, assume all registers are uninitialized. */ 2011 2012 static void 2013 df_mir_confluence_0 (basic_block bb) 2014 { 2015 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index); 2016 2017 bitmap_clear (&bb_info->in); 2018 } 2019 2020 2021 /* Forward confluence function that ignores fake edges. */ 2022 2023 static bool 2024 df_mir_confluence_n (edge e) 2025 { 2026 bitmap op1 = &df_mir_get_bb_info (e->dest->index)->in; 2027 bitmap op2 = &df_mir_get_bb_info (e->src->index)->out; 2028 2029 if (e->flags & EDGE_FAKE) 2030 return false; 2031 2032 /* A register is must-initialized at the entry of a basic block iff it is 2033 must-initialized at the exit of all the predecessors. */ 2034 return bitmap_and_into (op1, op2); 2035 } 2036 2037 2038 /* Transfer function for the forwards must-initialized problem. */ 2039 2040 static bool 2041 df_mir_transfer_function (int bb_index) 2042 { 2043 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index); 2044 bitmap in = &bb_info->in; 2045 bitmap out = &bb_info->out; 2046 bitmap gen = &bb_info->gen; 2047 bitmap kill = &bb_info->kill; 2048 2049 return bitmap_ior_and_compl (out, gen, in, kill); 2050 } 2051 2052 2053 /* Free all storage associated with the problem. */ 2054 2055 static void 2056 df_mir_free (void) 2057 { 2058 struct df_mir_problem_data *problem_data 2059 = (struct df_mir_problem_data *) df_mir->problem_data; 2060 if (df_mir->block_info) 2061 { 2062 df_mir->block_info_size = 0; 2063 free (df_mir->block_info); 2064 df_mir->block_info = NULL; 2065 bitmap_obstack_release (&problem_data->mir_bitmaps); 2066 free (problem_data); 2067 df_mir->problem_data = NULL; 2068 } 2069 free (df_mir); 2070 } 2071 2072 2073 /* Debugging info at top of bb. */ 2074 2075 static void 2076 df_mir_top_dump (basic_block bb, FILE *file) 2077 { 2078 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index); 2079 2080 if (!bb_info) 2081 return; 2082 2083 fprintf (file, ";; mir in \t"); 2084 df_print_regset (file, &bb_info->in); 2085 fprintf (file, ";; mir kill\t"); 2086 df_print_regset (file, &bb_info->kill); 2087 fprintf (file, ";; mir gen \t"); 2088 df_print_regset (file, &bb_info->gen); 2089 } 2090 2091 /* Debugging info at bottom of bb. */ 2092 2093 static void 2094 df_mir_bottom_dump (basic_block bb, FILE *file) 2095 { 2096 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index); 2097 2098 if (!bb_info) 2099 return; 2100 2101 fprintf (file, ";; mir out \t"); 2102 df_print_regset (file, &bb_info->out); 2103 } 2104 2105 2106 /* Build the datastructure to verify that the solution to the dataflow 2107 equations is not dirty. */ 2108 2109 static void 2110 df_mir_verify_solution_start (void) 2111 { 2112 basic_block bb; 2113 struct df_mir_problem_data *problem_data; 2114 if (df_mir->solutions_dirty) 2115 return; 2116 2117 /* Set it true so that the solution is recomputed. */ 2118 df_mir->solutions_dirty = true; 2119 2120 problem_data = (struct df_mir_problem_data *) df_mir->problem_data; 2121 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 2122 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 2123 bitmap_obstack_initialize (&problem_data->mir_bitmaps); 2124 2125 FOR_ALL_BB_FN (bb, cfun) 2126 { 2127 bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps); 2128 bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps); 2129 bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb)); 2130 bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb)); 2131 } 2132 } 2133 2134 2135 /* Compare the saved datastructure and the new solution to the dataflow 2136 equations. */ 2137 2138 static void 2139 df_mir_verify_solution_end (void) 2140 { 2141 struct df_mir_problem_data *problem_data; 2142 basic_block bb; 2143 2144 problem_data = (struct df_mir_problem_data *) df_mir->problem_data; 2145 if (!problem_data->out) 2146 return; 2147 2148 FOR_ALL_BB_FN (bb, cfun) 2149 { 2150 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb))) 2151 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb)))) 2152 gcc_unreachable (); 2153 } 2154 2155 /* Cannot delete them immediately because you may want to dump them 2156 if the comparison fails. */ 2157 FOR_ALL_BB_FN (bb, cfun) 2158 { 2159 bitmap_clear (&problem_data->in[bb->index]); 2160 bitmap_clear (&problem_data->out[bb->index]); 2161 } 2162 2163 free (problem_data->in); 2164 free (problem_data->out); 2165 bitmap_obstack_release (&problem_data->mir_bitmaps); 2166 free (problem_data); 2167 df_mir->problem_data = NULL; 2168 } 2169 2170 2171 /* All of the information associated with every instance of the problem. */ 2172 2173 static const struct df_problem problem_MIR = 2174 { 2175 DF_MIR, /* Problem id. */ 2176 DF_FORWARD, /* Direction. */ 2177 df_mir_alloc, /* Allocate the problem specific data. */ 2178 df_mir_reset, /* Reset global information. */ 2179 df_mir_free_bb_info, /* Free basic block info. */ 2180 df_mir_local_compute, /* Local compute function. */ 2181 df_mir_init, /* Init the solution specific data. */ 2182 df_worklist_dataflow, /* Worklist solver. */ 2183 df_mir_confluence_0, /* Confluence operator 0. */ 2184 df_mir_confluence_n, /* Confluence operator n. */ 2185 df_mir_transfer_function, /* Transfer function. */ 2186 NULL, /* Finalize function. */ 2187 df_mir_free, /* Free all of the problem information. */ 2188 df_mir_free, /* Remove this problem from the stack of dataflow problems. */ 2189 NULL, /* Debugging. */ 2190 df_mir_top_dump, /* Debugging start block. */ 2191 df_mir_bottom_dump, /* Debugging end block. */ 2192 NULL, /* Debugging start insn. */ 2193 NULL, /* Debugging end insn. */ 2194 df_mir_verify_solution_start, /* Incremental solution verify start. */ 2195 df_mir_verify_solution_end, /* Incremental solution verify end. */ 2196 NULL, /* Dependent problem. */ 2197 sizeof (struct df_mir_bb_info),/* Size of entry of block_info array. */ 2198 TV_DF_MIR, /* Timing variable. */ 2199 false /* Reset blocks on dropping out of blocks_to_analyze. */ 2200 }; 2201 2202 2203 /* Create a new DATAFLOW instance and add it to an existing instance 2204 of DF. */ 2205 2206 void 2207 df_mir_add_problem (void) 2208 { 2209 df_add_problem (&problem_MIR); 2210 /* These will be initialized when df_scan_blocks processes each 2211 block. */ 2212 df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack); 2213 } 2214 2215 2216 /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */ 2217 2218 void 2219 df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn, 2220 bitmap kill, bitmap gen) 2221 { 2222 df_ref def; 2223 2224 FOR_EACH_INSN_DEF (def, insn) 2225 { 2226 unsigned int regno = DF_REF_REGNO (def); 2227 2228 /* The order of GENs/KILLs matters, so if this def clobbers a reg, any 2229 previous gen is irrelevant (and reciprocally). Also, claim that a 2230 register is GEN only if it is in all cases. */ 2231 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) 2232 { 2233 bitmap_set_bit (kill, regno); 2234 bitmap_clear_bit (gen, regno); 2235 } 2236 /* In the worst case, partial and conditional defs can leave bits 2237 uninitialized, so assume they do not change anything. */ 2238 else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL)) 2239 { 2240 bitmap_set_bit (gen, regno); 2241 bitmap_clear_bit (kill, regno); 2242 } 2243 } 2244 } 2245 2246 /*---------------------------------------------------------------------------- 2247 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS 2248 2249 Link either the defs to the uses and / or the uses to the defs. 2250 2251 These problems are set up like the other dataflow problems so that 2252 they nicely fit into the framework. They are much simpler and only 2253 involve a single traversal of instructions and an examination of 2254 the reaching defs information (the dependent problem). 2255 ----------------------------------------------------------------------------*/ 2256 2257 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG)) 2258 2259 /* Create a du or ud chain from SRC to DST and link it into SRC. */ 2260 2261 struct df_link * 2262 df_chain_create (df_ref src, df_ref dst) 2263 { 2264 struct df_link *head = DF_REF_CHAIN (src); 2265 struct df_link *link = df_chain->block_pool->allocate (); 2266 2267 DF_REF_CHAIN (src) = link; 2268 link->next = head; 2269 link->ref = dst; 2270 return link; 2271 } 2272 2273 2274 /* Delete any du or ud chains that start at REF and point to 2275 TARGET. */ 2276 static void 2277 df_chain_unlink_1 (df_ref ref, df_ref target) 2278 { 2279 struct df_link *chain = DF_REF_CHAIN (ref); 2280 struct df_link *prev = NULL; 2281 2282 while (chain) 2283 { 2284 if (chain->ref == target) 2285 { 2286 if (prev) 2287 prev->next = chain->next; 2288 else 2289 DF_REF_CHAIN (ref) = chain->next; 2290 df_chain->block_pool->remove (chain); 2291 return; 2292 } 2293 prev = chain; 2294 chain = chain->next; 2295 } 2296 } 2297 2298 2299 /* Delete a du or ud chain that leave or point to REF. */ 2300 2301 void 2302 df_chain_unlink (df_ref ref) 2303 { 2304 struct df_link *chain = DF_REF_CHAIN (ref); 2305 while (chain) 2306 { 2307 struct df_link *next = chain->next; 2308 /* Delete the other side if it exists. */ 2309 df_chain_unlink_1 (chain->ref, ref); 2310 df_chain->block_pool->remove (chain); 2311 chain = next; 2312 } 2313 DF_REF_CHAIN (ref) = NULL; 2314 } 2315 2316 2317 /* Copy the du or ud chain starting at FROM_REF and attach it to 2318 TO_REF. */ 2319 2320 void 2321 df_chain_copy (df_ref to_ref, 2322 struct df_link *from_ref) 2323 { 2324 while (from_ref) 2325 { 2326 df_chain_create (to_ref, from_ref->ref); 2327 from_ref = from_ref->next; 2328 } 2329 } 2330 2331 2332 /* Remove this problem from the stack of dataflow problems. */ 2333 2334 static void 2335 df_chain_remove_problem (void) 2336 { 2337 bitmap_iterator bi; 2338 unsigned int bb_index; 2339 2340 /* Wholesale destruction of the old chains. */ 2341 if (df_chain->block_pool) 2342 delete df_chain->block_pool; 2343 2344 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi) 2345 { 2346 rtx_insn *insn; 2347 df_ref def, use; 2348 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 2349 2350 if (df_chain_problem_p (DF_DU_CHAIN)) 2351 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 2352 DF_REF_CHAIN (def) = NULL; 2353 if (df_chain_problem_p (DF_UD_CHAIN)) 2354 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 2355 DF_REF_CHAIN (use) = NULL; 2356 2357 FOR_BB_INSNS (bb, insn) 2358 if (INSN_P (insn)) 2359 { 2360 df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2361 if (df_chain_problem_p (DF_DU_CHAIN)) 2362 FOR_EACH_INSN_INFO_DEF (def, insn_info) 2363 DF_REF_CHAIN (def) = NULL; 2364 if (df_chain_problem_p (DF_UD_CHAIN)) 2365 { 2366 FOR_EACH_INSN_INFO_USE (use, insn_info) 2367 DF_REF_CHAIN (use) = NULL; 2368 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 2369 DF_REF_CHAIN (use) = NULL; 2370 } 2371 } 2372 } 2373 2374 bitmap_clear (df_chain->out_of_date_transfer_functions); 2375 df_chain->block_pool = NULL; 2376 } 2377 2378 2379 /* Remove the chain problem completely. */ 2380 2381 static void 2382 df_chain_fully_remove_problem (void) 2383 { 2384 df_chain_remove_problem (); 2385 BITMAP_FREE (df_chain->out_of_date_transfer_functions); 2386 free (df_chain); 2387 } 2388 2389 2390 /* Create def-use or use-def chains. */ 2391 2392 static void 2393 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 2394 { 2395 df_chain_remove_problem (); 2396 df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool"); 2397 df_chain->optional_p = true; 2398 } 2399 2400 2401 /* Reset all of the chains when the set of basic blocks changes. */ 2402 2403 static void 2404 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED) 2405 { 2406 df_chain_remove_problem (); 2407 } 2408 2409 2410 /* Create the chains for a list of USEs. */ 2411 2412 static void 2413 df_chain_create_bb_process_use (bitmap local_rd, 2414 df_ref use, 2415 int top_flag) 2416 { 2417 bitmap_iterator bi; 2418 unsigned int def_index; 2419 2420 for (; use; use = DF_REF_NEXT_LOC (use)) 2421 { 2422 unsigned int uregno = DF_REF_REGNO (use); 2423 if ((!(df->changeable_flags & DF_NO_HARD_REGS)) 2424 || (uregno >= FIRST_PSEUDO_REGISTER)) 2425 { 2426 /* Do not want to go through this for an uninitialized var. */ 2427 int count = DF_DEFS_COUNT (uregno); 2428 if (count) 2429 { 2430 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) 2431 { 2432 unsigned int first_index = DF_DEFS_BEGIN (uregno); 2433 unsigned int last_index = first_index + count - 1; 2434 2435 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi) 2436 { 2437 df_ref def; 2438 if (def_index > last_index) 2439 break; 2440 2441 def = DF_DEFS_GET (def_index); 2442 if (df_chain_problem_p (DF_DU_CHAIN)) 2443 df_chain_create (def, use); 2444 if (df_chain_problem_p (DF_UD_CHAIN)) 2445 df_chain_create (use, def); 2446 } 2447 } 2448 } 2449 } 2450 } 2451 } 2452 2453 2454 /* Create chains from reaching defs bitmaps for basic block BB. */ 2455 2456 static void 2457 df_chain_create_bb (unsigned int bb_index) 2458 { 2459 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 2460 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); 2461 rtx_insn *insn; 2462 bitmap_head cpy; 2463 2464 bitmap_initialize (&cpy, &bitmap_default_obstack); 2465 bitmap_copy (&cpy, &bb_info->in); 2466 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index); 2467 2468 /* Since we are going forwards, process the artificial uses first 2469 then the artificial defs second. */ 2470 2471 #ifdef EH_USES 2472 /* Create the chains for the artificial uses from the EH_USES at the 2473 beginning of the block. */ 2474 2475 /* Artificials are only hard regs. */ 2476 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 2477 df_chain_create_bb_process_use (&cpy, 2478 df_get_artificial_uses (bb->index), 2479 DF_REF_AT_TOP); 2480 #endif 2481 2482 df_rd_simulate_artificial_defs_at_top (bb, &cpy); 2483 2484 /* Process the regular instructions next. */ 2485 FOR_BB_INSNS (bb, insn) 2486 if (INSN_P (insn)) 2487 { 2488 unsigned int uid = INSN_UID (insn); 2489 2490 /* First scan the uses and link them up with the defs that remain 2491 in the cpy vector. */ 2492 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0); 2493 if (df->changeable_flags & DF_EQ_NOTES) 2494 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0); 2495 2496 /* Since we are going forwards, process the defs second. */ 2497 df_rd_simulate_one_insn (bb, insn, &cpy); 2498 } 2499 2500 /* Create the chains for the artificial uses of the hard registers 2501 at the end of the block. */ 2502 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 2503 df_chain_create_bb_process_use (&cpy, 2504 df_get_artificial_uses (bb->index), 2505 0); 2506 2507 bitmap_clear (&cpy); 2508 } 2509 2510 /* Create def-use chains from reaching use bitmaps for basic blocks 2511 in BLOCKS. */ 2512 2513 static void 2514 df_chain_finalize (bitmap all_blocks) 2515 { 2516 unsigned int bb_index; 2517 bitmap_iterator bi; 2518 2519 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 2520 { 2521 df_chain_create_bb (bb_index); 2522 } 2523 } 2524 2525 2526 /* Free all storage associated with the problem. */ 2527 2528 static void 2529 df_chain_free (void) 2530 { 2531 delete df_chain->block_pool; 2532 BITMAP_FREE (df_chain->out_of_date_transfer_functions); 2533 free (df_chain); 2534 } 2535 2536 2537 /* Debugging info. */ 2538 2539 static void 2540 df_chain_bb_dump (basic_block bb, FILE *file, bool top) 2541 { 2542 /* Artificials are only hard regs. */ 2543 if (df->changeable_flags & DF_NO_HARD_REGS) 2544 return; 2545 if (df_chain_problem_p (DF_UD_CHAIN)) 2546 { 2547 df_ref use; 2548 2549 fprintf (file, 2550 ";; UD chains for artificial uses at %s\n", 2551 top ? "top" : "bottom"); 2552 FOR_EACH_ARTIFICIAL_USE (use, bb->index) 2553 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) 2554 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP))) 2555 { 2556 fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); 2557 df_chain_dump (DF_REF_CHAIN (use), file); 2558 fprintf (file, "\n"); 2559 } 2560 } 2561 if (df_chain_problem_p (DF_DU_CHAIN)) 2562 { 2563 df_ref def; 2564 2565 fprintf (file, 2566 ";; DU chains for artificial defs at %s\n", 2567 top ? "top" : "bottom"); 2568 FOR_EACH_ARTIFICIAL_DEF (def, bb->index) 2569 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) 2570 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP))) 2571 { 2572 fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); 2573 df_chain_dump (DF_REF_CHAIN (def), file); 2574 fprintf (file, "\n"); 2575 } 2576 } 2577 } 2578 2579 static void 2580 df_chain_top_dump (basic_block bb, FILE *file) 2581 { 2582 df_chain_bb_dump (bb, file, /*top=*/true); 2583 } 2584 2585 static void 2586 df_chain_bottom_dump (basic_block bb, FILE *file) 2587 { 2588 df_chain_bb_dump (bb, file, /*top=*/false); 2589 } 2590 2591 static void 2592 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file) 2593 { 2594 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn)) 2595 { 2596 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2597 df_ref use; 2598 2599 fprintf (file, ";; UD chains for insn luid %d uid %d\n", 2600 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn)); 2601 FOR_EACH_INSN_INFO_USE (use, insn_info) 2602 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use)) 2603 || !(df->changeable_flags & DF_NO_HARD_REGS)) 2604 { 2605 fprintf (file, ";; reg %d ", DF_REF_REGNO (use)); 2606 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) 2607 fprintf (file, "read/write "); 2608 df_chain_dump (DF_REF_CHAIN (use), file); 2609 fprintf (file, "\n"); 2610 } 2611 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 2612 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use)) 2613 || !(df->changeable_flags & DF_NO_HARD_REGS)) 2614 { 2615 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use)); 2616 df_chain_dump (DF_REF_CHAIN (use), file); 2617 fprintf (file, "\n"); 2618 } 2619 } 2620 } 2621 2622 static void 2623 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file) 2624 { 2625 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn)) 2626 { 2627 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2628 df_ref def; 2629 fprintf (file, ";; DU chains for insn luid %d uid %d\n", 2630 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn)); 2631 FOR_EACH_INSN_INFO_DEF (def, insn_info) 2632 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def)) 2633 || !(df->changeable_flags & DF_NO_HARD_REGS)) 2634 { 2635 fprintf (file, ";; reg %d ", DF_REF_REGNO (def)); 2636 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE) 2637 fprintf (file, "read/write "); 2638 df_chain_dump (DF_REF_CHAIN (def), file); 2639 fprintf (file, "\n"); 2640 } 2641 fprintf (file, "\n"); 2642 } 2643 } 2644 2645 static const struct df_problem problem_CHAIN = 2646 { 2647 DF_CHAIN, /* Problem id. */ 2648 DF_NONE, /* Direction. */ 2649 df_chain_alloc, /* Allocate the problem specific data. */ 2650 df_chain_reset, /* Reset global information. */ 2651 NULL, /* Free basic block info. */ 2652 NULL, /* Local compute function. */ 2653 NULL, /* Init the solution specific data. */ 2654 NULL, /* Iterative solver. */ 2655 NULL, /* Confluence operator 0. */ 2656 NULL, /* Confluence operator n. */ 2657 NULL, /* Transfer function. */ 2658 df_chain_finalize, /* Finalize function. */ 2659 df_chain_free, /* Free all of the problem information. */ 2660 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */ 2661 NULL, /* Debugging. */ 2662 df_chain_top_dump, /* Debugging start block. */ 2663 df_chain_bottom_dump, /* Debugging end block. */ 2664 df_chain_insn_top_dump, /* Debugging start insn. */ 2665 df_chain_insn_bottom_dump, /* Debugging end insn. */ 2666 NULL, /* Incremental solution verify start. */ 2667 NULL, /* Incremental solution verify end. */ 2668 &problem_RD, /* Dependent problem. */ 2669 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */ 2670 TV_DF_CHAIN, /* Timing variable. */ 2671 false /* Reset blocks on dropping out of blocks_to_analyze. */ 2672 }; 2673 2674 2675 /* Create a new DATAFLOW instance and add it to an existing instance 2676 of DF. The returned structure is what is used to get at the 2677 solution. */ 2678 2679 void 2680 df_chain_add_problem (unsigned int chain_flags) 2681 { 2682 df_add_problem (&problem_CHAIN); 2683 df_chain->local_flags = chain_flags; 2684 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack); 2685 } 2686 2687 #undef df_chain_problem_p 2688 2689 2690 /*---------------------------------------------------------------------------- 2691 WORD LEVEL LIVE REGISTERS 2692 2693 Find the locations in the function where any use of a pseudo can 2694 reach in the backwards direction. In and out bitvectors are built 2695 for each basic block. We only track pseudo registers that have a 2696 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and 2697 contain two bits corresponding to each of the subwords. 2698 2699 ----------------------------------------------------------------------------*/ 2700 2701 /* Private data used to verify the solution for this problem. */ 2702 struct df_word_lr_problem_data 2703 { 2704 /* An obstack for the bitmaps we need for this problem. */ 2705 bitmap_obstack word_lr_bitmaps; 2706 }; 2707 2708 2709 /* Free basic block info. */ 2710 2711 static void 2712 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 2713 void *vbb_info) 2714 { 2715 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info; 2716 if (bb_info) 2717 { 2718 bitmap_clear (&bb_info->use); 2719 bitmap_clear (&bb_info->def); 2720 bitmap_clear (&bb_info->in); 2721 bitmap_clear (&bb_info->out); 2722 } 2723 } 2724 2725 2726 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are 2727 not touched unless the block is new. */ 2728 2729 static void 2730 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 2731 { 2732 unsigned int bb_index; 2733 bitmap_iterator bi; 2734 basic_block bb; 2735 struct df_word_lr_problem_data *problem_data 2736 = XNEW (struct df_word_lr_problem_data); 2737 2738 df_word_lr->problem_data = problem_data; 2739 2740 df_grow_bb_info (df_word_lr); 2741 2742 /* Create the mapping from regnos to slots. This does not change 2743 unless the problem is destroyed and recreated. In particular, if 2744 we end up deleting the only insn that used a subreg, we do not 2745 want to redo the mapping because this would invalidate everything 2746 else. */ 2747 2748 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps); 2749 2750 FOR_EACH_BB_FN (bb, cfun) 2751 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index); 2752 2753 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK); 2754 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK); 2755 2756 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi) 2757 { 2758 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); 2759 2760 /* When bitmaps are already initialized, just clear them. */ 2761 if (bb_info->use.obstack) 2762 { 2763 bitmap_clear (&bb_info->def); 2764 bitmap_clear (&bb_info->use); 2765 } 2766 else 2767 { 2768 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps); 2769 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps); 2770 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps); 2771 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps); 2772 } 2773 } 2774 2775 df_word_lr->optional_p = true; 2776 } 2777 2778 2779 /* Reset the global solution for recalculation. */ 2780 2781 static void 2782 df_word_lr_reset (bitmap all_blocks) 2783 { 2784 unsigned int bb_index; 2785 bitmap_iterator bi; 2786 2787 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 2788 { 2789 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); 2790 gcc_assert (bb_info); 2791 bitmap_clear (&bb_info->in); 2792 bitmap_clear (&bb_info->out); 2793 } 2794 } 2795 2796 /* Examine REF, and if it is for a reg we're interested in, set or 2797 clear the bits corresponding to its subwords from the bitmap 2798 according to IS_SET. LIVE is the bitmap we should update. We do 2799 not track hard regs or pseudos of any size other than 2 * 2800 UNITS_PER_WORD. 2801 We return true if we changed the bitmap, or if we encountered a register 2802 we're not tracking. */ 2803 2804 bool 2805 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live) 2806 { 2807 rtx orig_reg = DF_REF_REG (ref); 2808 rtx reg = orig_reg; 2809 machine_mode reg_mode; 2810 unsigned regno; 2811 /* Left at -1 for whole accesses. */ 2812 int which_subword = -1; 2813 bool changed = false; 2814 2815 if (GET_CODE (reg) == SUBREG) 2816 reg = SUBREG_REG (orig_reg); 2817 regno = REGNO (reg); 2818 reg_mode = GET_MODE (reg); 2819 if (regno < FIRST_PSEUDO_REGISTER 2820 || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD) 2821 return true; 2822 2823 if (GET_CODE (orig_reg) == SUBREG 2824 && df_read_modify_subreg_p (orig_reg)) 2825 { 2826 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL)); 2827 if (subreg_lowpart_p (orig_reg)) 2828 which_subword = 0; 2829 else 2830 which_subword = 1; 2831 } 2832 if (is_set) 2833 { 2834 if (which_subword != 1) 2835 changed |= bitmap_set_bit (live, regno * 2); 2836 if (which_subword != 0) 2837 changed |= bitmap_set_bit (live, regno * 2 + 1); 2838 } 2839 else 2840 { 2841 if (which_subword != 1) 2842 changed |= bitmap_clear_bit (live, regno * 2); 2843 if (which_subword != 0) 2844 changed |= bitmap_clear_bit (live, regno * 2 + 1); 2845 } 2846 return changed; 2847 } 2848 2849 /* Compute local live register info for basic block BB. */ 2850 2851 static void 2852 df_word_lr_bb_local_compute (unsigned int bb_index) 2853 { 2854 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 2855 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); 2856 rtx_insn *insn; 2857 df_ref def, use; 2858 2859 /* Ensure that artificial refs don't contain references to pseudos. */ 2860 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 2861 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER); 2862 2863 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 2864 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER); 2865 2866 FOR_BB_INSNS_REVERSE (bb, insn) 2867 { 2868 if (!NONDEBUG_INSN_P (insn)) 2869 continue; 2870 2871 df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2872 FOR_EACH_INSN_INFO_DEF (def, insn_info) 2873 /* If the def is to only part of the reg, it does 2874 not kill the other defs that reach here. */ 2875 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL))) 2876 { 2877 df_word_lr_mark_ref (def, true, &bb_info->def); 2878 df_word_lr_mark_ref (def, false, &bb_info->use); 2879 } 2880 FOR_EACH_INSN_INFO_USE (use, insn_info) 2881 df_word_lr_mark_ref (use, true, &bb_info->use); 2882 } 2883 } 2884 2885 2886 /* Compute local live register info for each basic block within BLOCKS. */ 2887 2888 static void 2889 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) 2890 { 2891 unsigned int bb_index; 2892 bitmap_iterator bi; 2893 2894 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi) 2895 { 2896 if (bb_index == EXIT_BLOCK) 2897 { 2898 unsigned regno; 2899 bitmap_iterator bi; 2900 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER, 2901 regno, bi) 2902 gcc_unreachable (); 2903 } 2904 else 2905 df_word_lr_bb_local_compute (bb_index); 2906 } 2907 2908 bitmap_clear (df_word_lr->out_of_date_transfer_functions); 2909 } 2910 2911 2912 /* Initialize the solution vectors. */ 2913 2914 static void 2915 df_word_lr_init (bitmap all_blocks) 2916 { 2917 unsigned int bb_index; 2918 bitmap_iterator bi; 2919 2920 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 2921 { 2922 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); 2923 bitmap_copy (&bb_info->in, &bb_info->use); 2924 bitmap_clear (&bb_info->out); 2925 } 2926 } 2927 2928 2929 /* Confluence function that ignores fake edges. */ 2930 2931 static bool 2932 df_word_lr_confluence_n (edge e) 2933 { 2934 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out; 2935 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in; 2936 2937 return bitmap_ior_into (op1, op2); 2938 } 2939 2940 2941 /* Transfer function. */ 2942 2943 static bool 2944 df_word_lr_transfer_function (int bb_index) 2945 { 2946 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index); 2947 bitmap in = &bb_info->in; 2948 bitmap out = &bb_info->out; 2949 bitmap use = &bb_info->use; 2950 bitmap def = &bb_info->def; 2951 2952 return bitmap_ior_and_compl (in, use, out, def); 2953 } 2954 2955 2956 /* Free all storage associated with the problem. */ 2957 2958 static void 2959 df_word_lr_free (void) 2960 { 2961 struct df_word_lr_problem_data *problem_data 2962 = (struct df_word_lr_problem_data *)df_word_lr->problem_data; 2963 2964 if (df_word_lr->block_info) 2965 { 2966 df_word_lr->block_info_size = 0; 2967 free (df_word_lr->block_info); 2968 df_word_lr->block_info = NULL; 2969 } 2970 2971 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions); 2972 bitmap_obstack_release (&problem_data->word_lr_bitmaps); 2973 free (problem_data); 2974 free (df_word_lr); 2975 } 2976 2977 2978 /* Debugging info at top of bb. */ 2979 2980 static void 2981 df_word_lr_top_dump (basic_block bb, FILE *file) 2982 { 2983 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index); 2984 if (!bb_info) 2985 return; 2986 2987 fprintf (file, ";; blr in \t"); 2988 df_print_word_regset (file, &bb_info->in); 2989 fprintf (file, ";; blr use \t"); 2990 df_print_word_regset (file, &bb_info->use); 2991 fprintf (file, ";; blr def \t"); 2992 df_print_word_regset (file, &bb_info->def); 2993 } 2994 2995 2996 /* Debugging info at bottom of bb. */ 2997 2998 static void 2999 df_word_lr_bottom_dump (basic_block bb, FILE *file) 3000 { 3001 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index); 3002 if (!bb_info) 3003 return; 3004 3005 fprintf (file, ";; blr out \t"); 3006 df_print_word_regset (file, &bb_info->out); 3007 } 3008 3009 3010 /* All of the information associated with every instance of the problem. */ 3011 3012 static const struct df_problem problem_WORD_LR = 3013 { 3014 DF_WORD_LR, /* Problem id. */ 3015 DF_BACKWARD, /* Direction. */ 3016 df_word_lr_alloc, /* Allocate the problem specific data. */ 3017 df_word_lr_reset, /* Reset global information. */ 3018 df_word_lr_free_bb_info, /* Free basic block info. */ 3019 df_word_lr_local_compute, /* Local compute function. */ 3020 df_word_lr_init, /* Init the solution specific data. */ 3021 df_worklist_dataflow, /* Worklist solver. */ 3022 NULL, /* Confluence operator 0. */ 3023 df_word_lr_confluence_n, /* Confluence operator n. */ 3024 df_word_lr_transfer_function, /* Transfer function. */ 3025 NULL, /* Finalize function. */ 3026 df_word_lr_free, /* Free all of the problem information. */ 3027 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */ 3028 NULL, /* Debugging. */ 3029 df_word_lr_top_dump, /* Debugging start block. */ 3030 df_word_lr_bottom_dump, /* Debugging end block. */ 3031 NULL, /* Debugging start insn. */ 3032 NULL, /* Debugging end insn. */ 3033 NULL, /* Incremental solution verify start. */ 3034 NULL, /* Incremental solution verify end. */ 3035 NULL, /* Dependent problem. */ 3036 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */ 3037 TV_DF_WORD_LR, /* Timing variable. */ 3038 false /* Reset blocks on dropping out of blocks_to_analyze. */ 3039 }; 3040 3041 3042 /* Create a new DATAFLOW instance and add it to an existing instance 3043 of DF. The returned structure is what is used to get at the 3044 solution. */ 3045 3046 void 3047 df_word_lr_add_problem (void) 3048 { 3049 df_add_problem (&problem_WORD_LR); 3050 /* These will be initialized when df_scan_blocks processes each 3051 block. */ 3052 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack); 3053 } 3054 3055 3056 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed 3057 any bits, which is used by the caller to determine whether a set is 3058 necessary. We also return true if there are other reasons not to delete 3059 an insn. */ 3060 3061 bool 3062 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live) 3063 { 3064 bool changed = false; 3065 df_ref def; 3066 3067 FOR_EACH_INSN_DEF (def, insn) 3068 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL) 3069 changed = true; 3070 else 3071 changed |= df_word_lr_mark_ref (def, false, live); 3072 return changed; 3073 } 3074 3075 3076 /* Simulate the effects of the uses of INSN on LIVE. */ 3077 3078 void 3079 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live) 3080 { 3081 df_ref use; 3082 3083 FOR_EACH_INSN_USE (use, insn) 3084 df_word_lr_mark_ref (use, true, live); 3085 } 3086 3087 /*---------------------------------------------------------------------------- 3088 This problem computes REG_DEAD and REG_UNUSED notes. 3089 ----------------------------------------------------------------------------*/ 3090 3091 static void 3092 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 3093 { 3094 df_note->optional_p = true; 3095 } 3096 3097 /* This is only used if REG_DEAD_DEBUGGING is in effect. */ 3098 static void 3099 df_print_note (const char *prefix, rtx_insn *insn, rtx note) 3100 { 3101 if (dump_file) 3102 { 3103 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn)); 3104 print_rtl (dump_file, note); 3105 fprintf (dump_file, "\n"); 3106 } 3107 } 3108 3109 3110 /* After reg-stack, the x86 floating point stack regs are difficult to 3111 analyze because of all of the pushes, pops and rotations. Thus, we 3112 just leave the notes alone. */ 3113 3114 #ifdef STACK_REGS 3115 static inline bool 3116 df_ignore_stack_reg (int regno) 3117 { 3118 return regstack_completed 3119 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG); 3120 } 3121 #else 3122 static inline bool 3123 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED) 3124 { 3125 return false; 3126 } 3127 #endif 3128 3129 3130 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */ 3131 3132 static void 3133 df_remove_dead_and_unused_notes (rtx_insn *insn) 3134 { 3135 rtx *pprev = ®_NOTES (insn); 3136 rtx link = *pprev; 3137 3138 while (link) 3139 { 3140 switch (REG_NOTE_KIND (link)) 3141 { 3142 case REG_DEAD: 3143 /* After reg-stack, we need to ignore any unused notes 3144 for the stack registers. */ 3145 if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) 3146 { 3147 pprev = &XEXP (link, 1); 3148 link = *pprev; 3149 } 3150 else 3151 { 3152 rtx next = XEXP (link, 1); 3153 if (REG_DEAD_DEBUGGING) 3154 df_print_note ("deleting: ", insn, link); 3155 free_EXPR_LIST_node (link); 3156 *pprev = link = next; 3157 } 3158 break; 3159 3160 case REG_UNUSED: 3161 /* After reg-stack, we need to ignore any unused notes 3162 for the stack registers. */ 3163 if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) 3164 { 3165 pprev = &XEXP (link, 1); 3166 link = *pprev; 3167 } 3168 else 3169 { 3170 rtx next = XEXP (link, 1); 3171 if (REG_DEAD_DEBUGGING) 3172 df_print_note ("deleting: ", insn, link); 3173 free_EXPR_LIST_node (link); 3174 *pprev = link = next; 3175 } 3176 break; 3177 3178 default: 3179 pprev = &XEXP (link, 1); 3180 link = *pprev; 3181 break; 3182 } 3183 } 3184 } 3185 3186 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE 3187 as the bitmap of currently live registers. */ 3188 3189 static void 3190 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live) 3191 { 3192 rtx *pprev = ®_NOTES (insn); 3193 rtx link = *pprev; 3194 3195 while (link) 3196 { 3197 switch (REG_NOTE_KIND (link)) 3198 { 3199 case REG_EQUAL: 3200 case REG_EQUIV: 3201 { 3202 /* Remove the notes that refer to dead registers. As we have at most 3203 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note 3204 so we need to purge the complete EQ_USES vector when removing 3205 the note using df_notes_rescan. */ 3206 df_ref use; 3207 bool deleted = false; 3208 3209 FOR_EACH_INSN_EQ_USE (use, insn) 3210 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER 3211 && DF_REF_LOC (use) 3212 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE) 3213 && !bitmap_bit_p (live, DF_REF_REGNO (use)) 3214 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0))) 3215 { 3216 deleted = true; 3217 break; 3218 } 3219 if (deleted) 3220 { 3221 rtx next; 3222 if (REG_DEAD_DEBUGGING) 3223 df_print_note ("deleting: ", insn, link); 3224 next = XEXP (link, 1); 3225 free_EXPR_LIST_node (link); 3226 *pprev = link = next; 3227 df_notes_rescan (insn); 3228 } 3229 else 3230 { 3231 pprev = &XEXP (link, 1); 3232 link = *pprev; 3233 } 3234 break; 3235 } 3236 3237 default: 3238 pprev = &XEXP (link, 1); 3239 link = *pprev; 3240 break; 3241 } 3242 } 3243 } 3244 3245 /* Set a NOTE_TYPE note for REG in INSN. */ 3246 3247 static inline void 3248 df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg) 3249 { 3250 gcc_checking_assert (!DEBUG_INSN_P (insn)); 3251 add_reg_note (insn, note_type, reg); 3252 } 3253 3254 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its 3255 arguments. Return true if the register value described by MWS's 3256 mw_reg is known to be completely unused, and if mw_reg can therefore 3257 be used in a REG_UNUSED note. */ 3258 3259 static bool 3260 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws, 3261 bitmap live, bitmap artificial_uses) 3262 { 3263 unsigned int r; 3264 3265 /* If MWS describes a partial reference, create REG_UNUSED notes for 3266 individual hard registers. */ 3267 if (mws->flags & DF_REF_PARTIAL) 3268 return false; 3269 3270 /* Likewise if some part of the register is used. */ 3271 for (r = mws->start_regno; r <= mws->end_regno; r++) 3272 if (bitmap_bit_p (live, r) 3273 || bitmap_bit_p (artificial_uses, r)) 3274 return false; 3275 3276 gcc_assert (REG_P (mws->mw_reg)); 3277 return true; 3278 } 3279 3280 3281 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN 3282 based on the bits in LIVE. Do not generate notes for registers in 3283 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are 3284 not generated if the reg is both read and written by the 3285 instruction. 3286 */ 3287 3288 static void 3289 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws, 3290 bitmap live, bitmap do_not_gen, 3291 bitmap artificial_uses, 3292 struct dead_debug_local *debug) 3293 { 3294 unsigned int r; 3295 3296 if (REG_DEAD_DEBUGGING && dump_file) 3297 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n", 3298 mws->start_regno, mws->end_regno); 3299 3300 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses)) 3301 { 3302 unsigned int regno = mws->start_regno; 3303 df_set_note (REG_UNUSED, insn, mws->mw_reg); 3304 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG); 3305 3306 if (REG_DEAD_DEBUGGING) 3307 df_print_note ("adding 1: ", insn, REG_NOTES (insn)); 3308 3309 bitmap_set_bit (do_not_gen, regno); 3310 /* Only do this if the value is totally dead. */ 3311 } 3312 else 3313 for (r = mws->start_regno; r <= mws->end_regno; r++) 3314 { 3315 if (!bitmap_bit_p (live, r) 3316 && !bitmap_bit_p (artificial_uses, r)) 3317 { 3318 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]); 3319 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG); 3320 if (REG_DEAD_DEBUGGING) 3321 df_print_note ("adding 2: ", insn, REG_NOTES (insn)); 3322 } 3323 bitmap_set_bit (do_not_gen, r); 3324 } 3325 } 3326 3327 3328 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its 3329 arguments. Return true if the register value described by MWS's 3330 mw_reg is known to be completely dead, and if mw_reg can therefore 3331 be used in a REG_DEAD note. */ 3332 3333 static bool 3334 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws, 3335 bitmap live, bitmap artificial_uses, 3336 bitmap do_not_gen) 3337 { 3338 unsigned int r; 3339 3340 /* If MWS describes a partial reference, create REG_DEAD notes for 3341 individual hard registers. */ 3342 if (mws->flags & DF_REF_PARTIAL) 3343 return false; 3344 3345 /* Likewise if some part of the register is not dead. */ 3346 for (r = mws->start_regno; r <= mws->end_regno; r++) 3347 if (bitmap_bit_p (live, r) 3348 || bitmap_bit_p (artificial_uses, r) 3349 || bitmap_bit_p (do_not_gen, r)) 3350 return false; 3351 3352 gcc_assert (REG_P (mws->mw_reg)); 3353 return true; 3354 } 3355 3356 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based 3357 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes 3358 from being set if the instruction both reads and writes the 3359 register. */ 3360 3361 static void 3362 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws, 3363 bitmap live, bitmap do_not_gen, 3364 bitmap artificial_uses, bool *added_notes_p) 3365 { 3366 unsigned int r; 3367 bool is_debug = *added_notes_p; 3368 3369 *added_notes_p = false; 3370 3371 if (REG_DEAD_DEBUGGING && dump_file) 3372 { 3373 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =", 3374 mws->start_regno, mws->end_regno); 3375 df_print_regset (dump_file, do_not_gen); 3376 fprintf (dump_file, " live ="); 3377 df_print_regset (dump_file, live); 3378 fprintf (dump_file, " artificial uses ="); 3379 df_print_regset (dump_file, artificial_uses); 3380 } 3381 3382 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen)) 3383 { 3384 if (is_debug) 3385 { 3386 *added_notes_p = true; 3387 return; 3388 } 3389 /* Add a dead note for the entire multi word register. */ 3390 df_set_note (REG_DEAD, insn, mws->mw_reg); 3391 if (REG_DEAD_DEBUGGING) 3392 df_print_note ("adding 1: ", insn, REG_NOTES (insn)); 3393 } 3394 else 3395 { 3396 for (r = mws->start_regno; r <= mws->end_regno; r++) 3397 if (!bitmap_bit_p (live, r) 3398 && !bitmap_bit_p (artificial_uses, r) 3399 && !bitmap_bit_p (do_not_gen, r)) 3400 { 3401 if (is_debug) 3402 { 3403 *added_notes_p = true; 3404 return; 3405 } 3406 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]); 3407 if (REG_DEAD_DEBUGGING) 3408 df_print_note ("adding 2: ", insn, REG_NOTES (insn)); 3409 } 3410 } 3411 return; 3412 } 3413 3414 3415 /* Create a REG_UNUSED note if necessary for DEF in INSN updating 3416 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */ 3417 3418 static void 3419 df_create_unused_note (rtx_insn *insn, df_ref def, 3420 bitmap live, bitmap artificial_uses, 3421 struct dead_debug_local *debug) 3422 { 3423 unsigned int dregno = DF_REF_REGNO (def); 3424 3425 if (REG_DEAD_DEBUGGING && dump_file) 3426 { 3427 fprintf (dump_file, " regular looking at def "); 3428 df_ref_debug (def, dump_file); 3429 } 3430 3431 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG) 3432 || bitmap_bit_p (live, dregno) 3433 || bitmap_bit_p (artificial_uses, dregno) 3434 || df_ignore_stack_reg (dregno))) 3435 { 3436 rtx reg = (DF_REF_LOC (def)) 3437 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def); 3438 df_set_note (REG_UNUSED, insn, reg); 3439 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG); 3440 if (REG_DEAD_DEBUGGING) 3441 df_print_note ("adding 3: ", insn, REG_NOTES (insn)); 3442 } 3443 3444 return; 3445 } 3446 3447 3448 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register 3449 info: lifetime, bb, and number of defs and uses for basic block 3450 BB. The three bitvectors are scratch regs used here. */ 3451 3452 static void 3453 df_note_bb_compute (unsigned int bb_index, 3454 bitmap live, bitmap do_not_gen, bitmap artificial_uses) 3455 { 3456 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 3457 rtx_insn *insn; 3458 df_ref def, use; 3459 struct dead_debug_local debug; 3460 3461 dead_debug_local_init (&debug, NULL, NULL); 3462 3463 bitmap_copy (live, df_get_live_out (bb)); 3464 bitmap_clear (artificial_uses); 3465 3466 if (REG_DEAD_DEBUGGING && dump_file) 3467 { 3468 fprintf (dump_file, "live at bottom "); 3469 df_print_regset (dump_file, live); 3470 } 3471 3472 /* Process the artificial defs and uses at the bottom of the block 3473 to begin processing. */ 3474 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 3475 { 3476 if (REG_DEAD_DEBUGGING && dump_file) 3477 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def)); 3478 3479 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 3480 bitmap_clear_bit (live, DF_REF_REGNO (def)); 3481 } 3482 3483 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 3484 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) 3485 { 3486 unsigned int regno = DF_REF_REGNO (use); 3487 bitmap_set_bit (live, regno); 3488 3489 /* Notes are not generated for any of the artificial registers 3490 at the bottom of the block. */ 3491 bitmap_set_bit (artificial_uses, regno); 3492 } 3493 3494 if (REG_DEAD_DEBUGGING && dump_file) 3495 { 3496 fprintf (dump_file, "live before artificials out "); 3497 df_print_regset (dump_file, live); 3498 } 3499 3500 FOR_BB_INSNS_REVERSE (bb, insn) 3501 { 3502 if (!INSN_P (insn)) 3503 continue; 3504 3505 df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 3506 df_mw_hardreg *mw; 3507 int debug_insn; 3508 3509 debug_insn = DEBUG_INSN_P (insn); 3510 3511 bitmap_clear (do_not_gen); 3512 df_remove_dead_and_unused_notes (insn); 3513 3514 /* Process the defs. */ 3515 if (CALL_P (insn)) 3516 { 3517 if (REG_DEAD_DEBUGGING && dump_file) 3518 { 3519 fprintf (dump_file, "processing call %d\n live =", 3520 INSN_UID (insn)); 3521 df_print_regset (dump_file, live); 3522 } 3523 3524 /* We only care about real sets for calls. Clobbers cannot 3525 be depended on to really die. */ 3526 FOR_EACH_INSN_INFO_MW (mw, insn_info) 3527 if ((DF_MWS_REG_DEF_P (mw)) 3528 && !df_ignore_stack_reg (mw->start_regno)) 3529 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen, 3530 artificial_uses, &debug); 3531 3532 /* All of the defs except the return value are some sort of 3533 clobber. This code is for the return. */ 3534 FOR_EACH_INSN_INFO_DEF (def, insn_info) 3535 { 3536 unsigned int dregno = DF_REF_REGNO (def); 3537 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) 3538 { 3539 df_create_unused_note (insn, 3540 def, live, artificial_uses, &debug); 3541 bitmap_set_bit (do_not_gen, dregno); 3542 } 3543 3544 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL)) 3545 bitmap_clear_bit (live, dregno); 3546 } 3547 } 3548 else 3549 { 3550 /* Regular insn. */ 3551 FOR_EACH_INSN_INFO_MW (mw, insn_info) 3552 if (DF_MWS_REG_DEF_P (mw)) 3553 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen, 3554 artificial_uses, &debug); 3555 3556 FOR_EACH_INSN_INFO_DEF (def, insn_info) 3557 { 3558 unsigned int dregno = DF_REF_REGNO (def); 3559 df_create_unused_note (insn, 3560 def, live, artificial_uses, &debug); 3561 3562 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) 3563 bitmap_set_bit (do_not_gen, dregno); 3564 3565 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL)) 3566 bitmap_clear_bit (live, dregno); 3567 } 3568 } 3569 3570 /* Process the uses. */ 3571 FOR_EACH_INSN_INFO_MW (mw, insn_info) 3572 if (DF_MWS_REG_USE_P (mw) 3573 && !df_ignore_stack_reg (mw->start_regno)) 3574 { 3575 bool really_add_notes = debug_insn != 0; 3576 3577 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen, 3578 artificial_uses, 3579 &really_add_notes); 3580 3581 if (really_add_notes) 3582 debug_insn = -1; 3583 } 3584 3585 FOR_EACH_INSN_INFO_USE (use, insn_info) 3586 { 3587 unsigned int uregno = DF_REF_REGNO (use); 3588 3589 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn) 3590 { 3591 fprintf (dump_file, " regular looking at use "); 3592 df_ref_debug (use, dump_file); 3593 } 3594 3595 if (!bitmap_bit_p (live, uregno)) 3596 { 3597 if (debug_insn) 3598 { 3599 if (debug_insn > 0) 3600 { 3601 /* We won't add REG_UNUSED or REG_DEAD notes for 3602 these, so we don't have to mess with them in 3603 debug insns either. */ 3604 if (!bitmap_bit_p (artificial_uses, uregno) 3605 && !df_ignore_stack_reg (uregno)) 3606 dead_debug_add (&debug, use, uregno); 3607 continue; 3608 } 3609 break; 3610 } 3611 else 3612 dead_debug_insert_temp (&debug, uregno, insn, 3613 DEBUG_TEMP_BEFORE_WITH_REG); 3614 3615 if ( (!(DF_REF_FLAGS (use) 3616 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE))) 3617 && (!bitmap_bit_p (do_not_gen, uregno)) 3618 && (!bitmap_bit_p (artificial_uses, uregno)) 3619 && (!df_ignore_stack_reg (uregno))) 3620 { 3621 rtx reg = (DF_REF_LOC (use)) 3622 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use); 3623 df_set_note (REG_DEAD, insn, reg); 3624 3625 if (REG_DEAD_DEBUGGING) 3626 df_print_note ("adding 4: ", insn, REG_NOTES (insn)); 3627 } 3628 /* This register is now live. */ 3629 bitmap_set_bit (live, uregno); 3630 } 3631 } 3632 3633 df_remove_dead_eq_notes (insn, live); 3634 3635 if (debug_insn == -1) 3636 { 3637 /* ??? We could probably do better here, replacing dead 3638 registers with their definitions. */ 3639 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); 3640 df_insn_rescan_debug_internal (insn); 3641 } 3642 } 3643 3644 dead_debug_local_finish (&debug, NULL); 3645 } 3646 3647 3648 /* Compute register info: lifetime, bb, and number of defs and uses. */ 3649 static void 3650 df_note_compute (bitmap all_blocks) 3651 { 3652 unsigned int bb_index; 3653 bitmap_iterator bi; 3654 bitmap_head live, do_not_gen, artificial_uses; 3655 3656 bitmap_initialize (&live, &df_bitmap_obstack); 3657 bitmap_initialize (&do_not_gen, &df_bitmap_obstack); 3658 bitmap_initialize (&artificial_uses, &df_bitmap_obstack); 3659 3660 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 3661 { 3662 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead 3663 pseudos in debug insns because we don't always (re)visit blocks 3664 with death points after visiting dead uses. Even changing this 3665 loop to postorder would still leave room for visiting a death 3666 point before visiting a subsequent debug use. */ 3667 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses); 3668 } 3669 3670 bitmap_clear (&live); 3671 bitmap_clear (&do_not_gen); 3672 bitmap_clear (&artificial_uses); 3673 } 3674 3675 3676 /* Free all storage associated with the problem. */ 3677 3678 static void 3679 df_note_free (void) 3680 { 3681 free (df_note); 3682 } 3683 3684 3685 /* All of the information associated every instance of the problem. */ 3686 3687 static const struct df_problem problem_NOTE = 3688 { 3689 DF_NOTE, /* Problem id. */ 3690 DF_NONE, /* Direction. */ 3691 df_note_alloc, /* Allocate the problem specific data. */ 3692 NULL, /* Reset global information. */ 3693 NULL, /* Free basic block info. */ 3694 df_note_compute, /* Local compute function. */ 3695 NULL, /* Init the solution specific data. */ 3696 NULL, /* Iterative solver. */ 3697 NULL, /* Confluence operator 0. */ 3698 NULL, /* Confluence operator n. */ 3699 NULL, /* Transfer function. */ 3700 NULL, /* Finalize function. */ 3701 df_note_free, /* Free all of the problem information. */ 3702 df_note_free, /* Remove this problem from the stack of dataflow problems. */ 3703 NULL, /* Debugging. */ 3704 NULL, /* Debugging start block. */ 3705 NULL, /* Debugging end block. */ 3706 NULL, /* Debugging start insn. */ 3707 NULL, /* Debugging end insn. */ 3708 NULL, /* Incremental solution verify start. */ 3709 NULL, /* Incremental solution verify end. */ 3710 &problem_LR, /* Dependent problem. */ 3711 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */ 3712 TV_DF_NOTE, /* Timing variable. */ 3713 false /* Reset blocks on dropping out of blocks_to_analyze. */ 3714 }; 3715 3716 3717 /* Create a new DATAFLOW instance and add it to an existing instance 3718 of DF. The returned structure is what is used to get at the 3719 solution. */ 3720 3721 void 3722 df_note_add_problem (void) 3723 { 3724 df_add_problem (&problem_NOTE); 3725 } 3726 3727 3728 3729 3730 /*---------------------------------------------------------------------------- 3731 Functions for simulating the effects of single insns. 3732 3733 You can either simulate in the forwards direction, starting from 3734 the top of a block or the backwards direction from the end of the 3735 block. If you go backwards, defs are examined first to clear bits, 3736 then uses are examined to set bits. If you go forwards, defs are 3737 examined first to set bits, then REG_DEAD and REG_UNUSED notes 3738 are examined to clear bits. In either case, the result of examining 3739 a def can be undone (respectively by a use or a REG_UNUSED note). 3740 3741 If you start at the top of the block, use one of DF_LIVE_IN or 3742 DF_LR_IN. If you start at the bottom of the block use one of 3743 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS, 3744 THEY WILL BE DESTROYED. 3745 ----------------------------------------------------------------------------*/ 3746 3747 3748 /* Find the set of DEFs for INSN. */ 3749 3750 void 3751 df_simulate_find_defs (rtx_insn *insn, bitmap defs) 3752 { 3753 df_ref def; 3754 3755 FOR_EACH_INSN_DEF (def, insn) 3756 bitmap_set_bit (defs, DF_REF_REGNO (def)); 3757 } 3758 3759 /* Find the set of uses for INSN. This includes partial defs. */ 3760 3761 static void 3762 df_simulate_find_uses (rtx_insn *insn, bitmap uses) 3763 { 3764 df_ref def, use; 3765 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 3766 3767 FOR_EACH_INSN_INFO_DEF (def, insn_info) 3768 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)) 3769 bitmap_set_bit (uses, DF_REF_REGNO (def)); 3770 FOR_EACH_INSN_INFO_USE (use, insn_info) 3771 bitmap_set_bit (uses, DF_REF_REGNO (use)); 3772 } 3773 3774 /* Find the set of real DEFs, which are not clobbers, for INSN. */ 3775 3776 void 3777 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs) 3778 { 3779 df_ref def; 3780 3781 FOR_EACH_INSN_DEF (def, insn) 3782 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 3783 bitmap_set_bit (defs, DF_REF_REGNO (def)); 3784 } 3785 3786 3787 /* Simulate the effects of the defs of INSN on LIVE. */ 3788 3789 void 3790 df_simulate_defs (rtx_insn *insn, bitmap live) 3791 { 3792 df_ref def; 3793 3794 FOR_EACH_INSN_DEF (def, insn) 3795 { 3796 unsigned int dregno = DF_REF_REGNO (def); 3797 3798 /* If the def is to only part of the reg, it does 3799 not kill the other defs that reach here. */ 3800 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))) 3801 bitmap_clear_bit (live, dregno); 3802 } 3803 } 3804 3805 3806 /* Simulate the effects of the uses of INSN on LIVE. */ 3807 3808 void 3809 df_simulate_uses (rtx_insn *insn, bitmap live) 3810 { 3811 df_ref use; 3812 3813 if (DEBUG_INSN_P (insn)) 3814 return; 3815 3816 FOR_EACH_INSN_USE (use, insn) 3817 /* Add use to set of uses in this BB. */ 3818 bitmap_set_bit (live, DF_REF_REGNO (use)); 3819 } 3820 3821 3822 /* Add back the always live regs in BB to LIVE. */ 3823 3824 static inline void 3825 df_simulate_fixup_sets (basic_block bb, bitmap live) 3826 { 3827 /* These regs are considered always live so if they end up dying 3828 because of some def, we need to bring the back again. */ 3829 if (bb_has_eh_pred (bb)) 3830 bitmap_ior_into (live, &df->eh_block_artificial_uses); 3831 else 3832 bitmap_ior_into (live, &df->regular_block_artificial_uses); 3833 } 3834 3835 3836 /*---------------------------------------------------------------------------- 3837 The following three functions are used only for BACKWARDS scanning: 3838 i.e. they process the defs before the uses. 3839 3840 df_simulate_initialize_backwards should be called first with a 3841 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then 3842 df_simulate_one_insn_backwards should be called for each insn in 3843 the block, starting with the last one. Finally, 3844 df_simulate_finalize_backwards can be called to get a new value 3845 of the sets at the top of the block (this is rarely used). 3846 ----------------------------------------------------------------------------*/ 3847 3848 /* Apply the artificial uses and defs at the end of BB in a backwards 3849 direction. */ 3850 3851 void 3852 df_simulate_initialize_backwards (basic_block bb, bitmap live) 3853 { 3854 df_ref def, use; 3855 int bb_index = bb->index; 3856 3857 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 3858 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 3859 bitmap_clear_bit (live, DF_REF_REGNO (def)); 3860 3861 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 3862 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) 3863 bitmap_set_bit (live, DF_REF_REGNO (use)); 3864 } 3865 3866 3867 /* Simulate the backwards effects of INSN on the bitmap LIVE. */ 3868 3869 void 3870 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live) 3871 { 3872 if (!NONDEBUG_INSN_P (insn)) 3873 return; 3874 3875 df_simulate_defs (insn, live); 3876 df_simulate_uses (insn, live); 3877 df_simulate_fixup_sets (bb, live); 3878 } 3879 3880 3881 /* Apply the artificial uses and defs at the top of BB in a backwards 3882 direction. */ 3883 3884 void 3885 df_simulate_finalize_backwards (basic_block bb, bitmap live) 3886 { 3887 df_ref def; 3888 #ifdef EH_USES 3889 df_ref use; 3890 #endif 3891 int bb_index = bb->index; 3892 3893 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 3894 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 3895 bitmap_clear_bit (live, DF_REF_REGNO (def)); 3896 3897 #ifdef EH_USES 3898 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 3899 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) 3900 bitmap_set_bit (live, DF_REF_REGNO (use)); 3901 #endif 3902 } 3903 /*---------------------------------------------------------------------------- 3904 The following three functions are used only for FORWARDS scanning: 3905 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes. 3906 Thus it is important to add the DF_NOTES problem to the stack of 3907 problems computed before using these functions. 3908 3909 df_simulate_initialize_forwards should be called first with a 3910 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then 3911 df_simulate_one_insn_forwards should be called for each insn in 3912 the block, starting with the first one. 3913 ----------------------------------------------------------------------------*/ 3914 3915 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or 3916 DF_LR_IN for basic block BB, for forward scanning by marking artificial 3917 defs live. */ 3918 3919 void 3920 df_simulate_initialize_forwards (basic_block bb, bitmap live) 3921 { 3922 df_ref def; 3923 int bb_index = bb->index; 3924 3925 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 3926 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 3927 bitmap_set_bit (live, DF_REF_REGNO (def)); 3928 } 3929 3930 /* Simulate the forwards effects of INSN on the bitmap LIVE. */ 3931 3932 void 3933 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live) 3934 { 3935 rtx link; 3936 if (! INSN_P (insn)) 3937 return; 3938 3939 /* Make sure that DF_NOTE really is an active df problem. */ 3940 gcc_assert (df_note); 3941 3942 /* Note that this is the opposite as how the problem is defined, because 3943 in the LR problem defs _kill_ liveness. However, they do so backwards, 3944 while here the scan is performed forwards! So, first assume that the 3945 def is live, and if this is not true REG_UNUSED notes will rectify the 3946 situation. */ 3947 df_simulate_find_noclobber_defs (insn, live); 3948 3949 /* Clear all of the registers that go dead. */ 3950 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 3951 { 3952 switch (REG_NOTE_KIND (link)) 3953 { 3954 case REG_DEAD: 3955 case REG_UNUSED: 3956 { 3957 rtx reg = XEXP (link, 0); 3958 bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg)); 3959 } 3960 break; 3961 default: 3962 break; 3963 } 3964 } 3965 df_simulate_fixup_sets (bb, live); 3966 } 3967 3968 /* Used by the next two functions to encode information about the 3969 memory references we found. */ 3970 #define MEMREF_NORMAL 1 3971 #define MEMREF_VOLATILE 2 3972 3973 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */ 3974 3975 static int 3976 find_memory (rtx_insn *insn) 3977 { 3978 int flags = 0; 3979 subrtx_iterator::array_type array; 3980 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST) 3981 { 3982 const_rtx x = *iter; 3983 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x)) 3984 flags |= MEMREF_VOLATILE; 3985 else if (MEM_P (x)) 3986 { 3987 if (MEM_VOLATILE_P (x)) 3988 flags |= MEMREF_VOLATILE; 3989 else if (!MEM_READONLY_P (x)) 3990 flags |= MEMREF_NORMAL; 3991 } 3992 } 3993 return flags; 3994 } 3995 3996 /* A subroutine of can_move_insns_across_p called through note_stores. 3997 DATA points to an integer in which we set either the bit for 3998 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM 3999 of either kind. */ 4000 4001 static void 4002 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED, 4003 void *data ATTRIBUTE_UNUSED) 4004 { 4005 int *pflags = (int *)data; 4006 if (GET_CODE (x) == SUBREG) 4007 x = XEXP (x, 0); 4008 /* Treat stores to SP as stores to memory, this will prevent problems 4009 when there are references to the stack frame. */ 4010 if (x == stack_pointer_rtx) 4011 *pflags |= MEMREF_VOLATILE; 4012 if (!MEM_P (x)) 4013 return; 4014 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL; 4015 } 4016 4017 /* Scan BB backwards, using df_simulate functions to keep track of 4018 lifetimes, up to insn POINT. The result is stored in LIVE. */ 4019 4020 void 4021 simulate_backwards_to_point (basic_block bb, regset live, rtx point) 4022 { 4023 rtx_insn *insn; 4024 bitmap_copy (live, df_get_live_out (bb)); 4025 df_simulate_initialize_backwards (bb, live); 4026 4027 /* Scan and update life information until we reach the point we're 4028 interested in. */ 4029 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn)) 4030 df_simulate_one_insn_backwards (bb, insn, live); 4031 } 4032 4033 /* Return true if it is safe to move a group of insns, described by 4034 the range FROM to TO, backwards across another group of insns, 4035 described by ACROSS_FROM to ACROSS_TO. It is assumed that there 4036 are no insns between ACROSS_TO and FROM, but they may be in 4037 different basic blocks; MERGE_BB is the block from which the 4038 insns will be moved. The caller must pass in a regset MERGE_LIVE 4039 which specifies the registers live after TO. 4040 4041 This function may be called in one of two cases: either we try to 4042 move identical instructions from all successor blocks into their 4043 predecessor, or we try to move from only one successor block. If 4044 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with 4045 the second case. It should contain a set of registers live at the 4046 end of ACROSS_TO which must not be clobbered by moving the insns. 4047 In that case, we're also more careful about moving memory references 4048 and trapping insns. 4049 4050 We return false if it is not safe to move the entire group, but it 4051 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull, 4052 is set to point at the last moveable insn in such a case. */ 4053 4054 bool 4055 can_move_insns_across (rtx_insn *from, rtx_insn *to, 4056 rtx_insn *across_from, rtx_insn *across_to, 4057 basic_block merge_bb, regset merge_live, 4058 regset other_branch_live, rtx_insn **pmove_upto) 4059 { 4060 rtx_insn *insn, *next, *max_to; 4061 bitmap merge_set, merge_use, local_merge_live; 4062 bitmap test_set, test_use; 4063 unsigned i, fail = 0; 4064 bitmap_iterator bi; 4065 int memrefs_in_across = 0; 4066 int mem_sets_in_across = 0; 4067 bool trapping_insns_in_across = false; 4068 4069 if (pmove_upto != NULL) 4070 *pmove_upto = NULL; 4071 4072 /* Find real bounds, ignoring debug insns. */ 4073 while (!NONDEBUG_INSN_P (from) && from != to) 4074 from = NEXT_INSN (from); 4075 while (!NONDEBUG_INSN_P (to) && from != to) 4076 to = PREV_INSN (to); 4077 4078 for (insn = across_to; ; insn = next) 4079 { 4080 if (CALL_P (insn)) 4081 { 4082 if (RTL_CONST_OR_PURE_CALL_P (insn)) 4083 /* Pure functions can read from memory. Const functions can 4084 read from arguments that the ABI has forced onto the stack. 4085 Neither sort of read can be volatile. */ 4086 memrefs_in_across |= MEMREF_NORMAL; 4087 else 4088 { 4089 memrefs_in_across |= MEMREF_VOLATILE; 4090 mem_sets_in_across |= MEMREF_VOLATILE; 4091 } 4092 } 4093 if (NONDEBUG_INSN_P (insn)) 4094 { 4095 if (volatile_insn_p (PATTERN (insn))) 4096 return false; 4097 memrefs_in_across |= find_memory (insn); 4098 note_stores (PATTERN (insn), find_memory_stores, 4099 &mem_sets_in_across); 4100 /* This is used just to find sets of the stack pointer. */ 4101 memrefs_in_across |= mem_sets_in_across; 4102 trapping_insns_in_across |= may_trap_p (PATTERN (insn)); 4103 } 4104 next = PREV_INSN (insn); 4105 if (insn == across_from) 4106 break; 4107 } 4108 4109 /* Collect: 4110 MERGE_SET = set of registers set in MERGE_BB 4111 MERGE_USE = set of registers used in MERGE_BB and live at its top 4112 MERGE_LIVE = set of registers live at the point inside the MERGE 4113 range that we've reached during scanning 4114 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END. 4115 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END, 4116 and live before ACROSS_FROM. */ 4117 4118 merge_set = BITMAP_ALLOC (®_obstack); 4119 merge_use = BITMAP_ALLOC (®_obstack); 4120 local_merge_live = BITMAP_ALLOC (®_obstack); 4121 test_set = BITMAP_ALLOC (®_obstack); 4122 test_use = BITMAP_ALLOC (®_obstack); 4123 4124 /* Compute the set of registers set and used in the ACROSS range. */ 4125 if (other_branch_live != NULL) 4126 bitmap_copy (test_use, other_branch_live); 4127 df_simulate_initialize_backwards (merge_bb, test_use); 4128 for (insn = across_to; ; insn = next) 4129 { 4130 if (NONDEBUG_INSN_P (insn)) 4131 { 4132 df_simulate_find_defs (insn, test_set); 4133 df_simulate_defs (insn, test_use); 4134 df_simulate_uses (insn, test_use); 4135 } 4136 next = PREV_INSN (insn); 4137 if (insn == across_from) 4138 break; 4139 } 4140 4141 /* Compute an upper bound for the amount of insns moved, by finding 4142 the first insn in MERGE that sets a register in TEST_USE, or uses 4143 a register in TEST_SET. We also check for calls, trapping operations, 4144 and memory references. */ 4145 max_to = NULL; 4146 for (insn = from; ; insn = next) 4147 { 4148 if (CALL_P (insn)) 4149 break; 4150 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG) 4151 break; 4152 if (NONDEBUG_INSN_P (insn)) 4153 { 4154 if (may_trap_or_fault_p (PATTERN (insn)) 4155 && (trapping_insns_in_across 4156 || other_branch_live != NULL 4157 || volatile_insn_p (PATTERN (insn)))) 4158 break; 4159 4160 /* We cannot move memory stores past each other, or move memory 4161 reads past stores, at least not without tracking them and 4162 calling true_dependence on every pair. 4163 4164 If there is no other branch and no memory references or 4165 sets in the ACROSS range, we can move memory references 4166 freely, even volatile ones. 4167 4168 Otherwise, the rules are as follows: volatile memory 4169 references and stores can't be moved at all, and any type 4170 of memory reference can't be moved if there are volatile 4171 accesses or stores in the ACROSS range. That leaves 4172 normal reads, which can be moved, as the trapping case is 4173 dealt with elsewhere. */ 4174 if (other_branch_live != NULL || memrefs_in_across != 0) 4175 { 4176 int mem_ref_flags = 0; 4177 int mem_set_flags = 0; 4178 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags); 4179 mem_ref_flags = find_memory (insn); 4180 /* Catch sets of the stack pointer. */ 4181 mem_ref_flags |= mem_set_flags; 4182 4183 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE) 4184 break; 4185 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0) 4186 break; 4187 if (mem_set_flags != 0 4188 || (mem_sets_in_across != 0 && mem_ref_flags != 0)) 4189 break; 4190 } 4191 df_simulate_find_uses (insn, merge_use); 4192 /* We're only interested in uses which use a value live at 4193 the top, not one previously set in this block. */ 4194 bitmap_and_compl_into (merge_use, merge_set); 4195 df_simulate_find_defs (insn, merge_set); 4196 if (bitmap_intersect_p (merge_set, test_use) 4197 || bitmap_intersect_p (merge_use, test_set)) 4198 break; 4199 if (!HAVE_cc0 || !sets_cc0_p (insn)) 4200 max_to = insn; 4201 } 4202 next = NEXT_INSN (insn); 4203 if (insn == to) 4204 break; 4205 } 4206 if (max_to != to) 4207 fail = 1; 4208 4209 if (max_to == NULL_RTX || (fail && pmove_upto == NULL)) 4210 goto out; 4211 4212 /* Now, lower this upper bound by also taking into account that 4213 a range of insns moved across ACROSS must not leave a register 4214 live at the end that will be clobbered in ACROSS. We need to 4215 find a point where TEST_SET & LIVE == 0. 4216 4217 Insns in the MERGE range that set registers which are also set 4218 in the ACROSS range may still be moved as long as we also move 4219 later insns which use the results of the set, and make the 4220 register dead again. This is verified by the condition stated 4221 above. We only need to test it for registers that are set in 4222 the moved region. 4223 4224 MERGE_LIVE is provided by the caller and holds live registers after 4225 TO. */ 4226 bitmap_copy (local_merge_live, merge_live); 4227 for (insn = to; insn != max_to; insn = PREV_INSN (insn)) 4228 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live); 4229 4230 /* We're not interested in registers that aren't set in the moved 4231 region at all. */ 4232 bitmap_and_into (local_merge_live, merge_set); 4233 for (;;) 4234 { 4235 if (NONDEBUG_INSN_P (insn)) 4236 { 4237 if (!bitmap_intersect_p (test_set, local_merge_live) 4238 && (!HAVE_cc0 || !sets_cc0_p (insn))) 4239 { 4240 max_to = insn; 4241 break; 4242 } 4243 4244 df_simulate_one_insn_backwards (merge_bb, insn, 4245 local_merge_live); 4246 } 4247 if (insn == from) 4248 { 4249 fail = 1; 4250 goto out; 4251 } 4252 insn = PREV_INSN (insn); 4253 } 4254 4255 if (max_to != to) 4256 fail = 1; 4257 4258 if (pmove_upto) 4259 *pmove_upto = max_to; 4260 4261 /* For small register class machines, don't lengthen lifetimes of 4262 hard registers before reload. */ 4263 if (! reload_completed 4264 && targetm.small_register_classes_for_mode_p (VOIDmode)) 4265 { 4266 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi) 4267 { 4268 if (i < FIRST_PSEUDO_REGISTER 4269 && ! fixed_regs[i] 4270 && ! global_regs[i]) 4271 { 4272 fail = 1; 4273 break; 4274 } 4275 } 4276 } 4277 4278 out: 4279 BITMAP_FREE (merge_set); 4280 BITMAP_FREE (merge_use); 4281 BITMAP_FREE (local_merge_live); 4282 BITMAP_FREE (test_set); 4283 BITMAP_FREE (test_use); 4284 4285 return !fail; 4286 } 4287 4288 4289 /*---------------------------------------------------------------------------- 4290 MULTIPLE DEFINITIONS 4291 4292 Find the locations in the function reached by multiple definition sites 4293 for a live pseudo. In and out bitvectors are built for each basic 4294 block. They are restricted for efficiency to live registers. 4295 4296 The gen and kill sets for the problem are obvious. Together they 4297 include all defined registers in a basic block; the gen set includes 4298 registers where a partial or conditional or may-clobber definition is 4299 last in the BB, while the kill set includes registers with a complete 4300 definition coming last. However, the computation of the dataflow 4301 itself is interesting. 4302 4303 The idea behind it comes from SSA form's iterated dominance frontier 4304 criterion for inserting PHI functions. Just like in that case, we can use 4305 the dominance frontier to find places where multiple definitions meet; 4306 a register X defined in a basic block BB1 has multiple definitions in 4307 basic blocks in BB1's dominance frontier. 4308 4309 So, the in-set of a basic block BB2 is not just the union of the 4310 out-sets of BB2's predecessors, but includes some more bits that come 4311 from the basic blocks of whose dominance frontier BB2 is part (BB1 in 4312 the previous paragraph). I called this set the init-set of BB2. 4313 4314 (Note: I actually use the kill-set only to build the init-set. 4315 gen bits are anyway propagated from BB1 to BB2 by dataflow). 4316 4317 For example, if you have 4318 4319 BB1 : r10 = 0 4320 r11 = 0 4321 if <...> goto BB2 else goto BB3; 4322 4323 BB2 : r10 = 1 4324 r12 = 1 4325 goto BB3; 4326 4327 BB3 : 4328 4329 you have BB3 in BB2's dominance frontier but not in BB1's, so that the 4330 init-set of BB3 includes r10 and r12, but not r11. Note that we do 4331 not need to iterate the dominance frontier, because we do not insert 4332 anything like PHI functions there! Instead, dataflow will take care of 4333 propagating the information to BB3's successors. 4334 ---------------------------------------------------------------------------*/ 4335 4336 /* Private data used to verify the solution for this problem. */ 4337 struct df_md_problem_data 4338 { 4339 /* An obstack for the bitmaps we need for this problem. */ 4340 bitmap_obstack md_bitmaps; 4341 }; 4342 4343 /* Scratch var used by transfer functions. This is used to do md analysis 4344 only for live registers. */ 4345 static bitmap_head df_md_scratch; 4346 4347 4348 static void 4349 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 4350 void *vbb_info) 4351 { 4352 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info; 4353 if (bb_info) 4354 { 4355 bitmap_clear (&bb_info->kill); 4356 bitmap_clear (&bb_info->gen); 4357 bitmap_clear (&bb_info->init); 4358 bitmap_clear (&bb_info->in); 4359 bitmap_clear (&bb_info->out); 4360 } 4361 } 4362 4363 4364 /* Allocate or reset bitmaps for DF_MD. The solution bits are 4365 not touched unless the block is new. */ 4366 4367 static void 4368 df_md_alloc (bitmap all_blocks) 4369 { 4370 unsigned int bb_index; 4371 bitmap_iterator bi; 4372 struct df_md_problem_data *problem_data; 4373 4374 df_grow_bb_info (df_md); 4375 if (df_md->problem_data) 4376 problem_data = (struct df_md_problem_data *) df_md->problem_data; 4377 else 4378 { 4379 problem_data = XNEW (struct df_md_problem_data); 4380 df_md->problem_data = problem_data; 4381 bitmap_obstack_initialize (&problem_data->md_bitmaps); 4382 } 4383 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps); 4384 4385 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 4386 { 4387 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); 4388 /* When bitmaps are already initialized, just clear them. */ 4389 if (bb_info->init.obstack) 4390 { 4391 bitmap_clear (&bb_info->init); 4392 bitmap_clear (&bb_info->gen); 4393 bitmap_clear (&bb_info->kill); 4394 bitmap_clear (&bb_info->in); 4395 bitmap_clear (&bb_info->out); 4396 } 4397 else 4398 { 4399 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps); 4400 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps); 4401 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps); 4402 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps); 4403 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps); 4404 } 4405 } 4406 4407 df_md->optional_p = true; 4408 } 4409 4410 /* Add the effect of the top artificial defs of BB to the multiple definitions 4411 bitmap LOCAL_MD. */ 4412 4413 void 4414 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md) 4415 { 4416 int bb_index = bb->index; 4417 df_ref def; 4418 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 4419 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 4420 { 4421 unsigned int dregno = DF_REF_REGNO (def); 4422 if (DF_REF_FLAGS (def) 4423 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) 4424 bitmap_set_bit (local_md, dregno); 4425 else 4426 bitmap_clear_bit (local_md, dregno); 4427 } 4428 } 4429 4430 4431 /* Add the effect of the defs of INSN to the reaching definitions bitmap 4432 LOCAL_MD. */ 4433 4434 void 4435 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn, 4436 bitmap local_md) 4437 { 4438 df_ref def; 4439 4440 FOR_EACH_INSN_DEF (def, insn) 4441 { 4442 unsigned int dregno = DF_REF_REGNO (def); 4443 if ((!(df->changeable_flags & DF_NO_HARD_REGS)) 4444 || (dregno >= FIRST_PSEUDO_REGISTER)) 4445 { 4446 if (DF_REF_FLAGS (def) 4447 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) 4448 bitmap_set_bit (local_md, DF_REF_ID (def)); 4449 else 4450 bitmap_clear_bit (local_md, DF_REF_ID (def)); 4451 } 4452 } 4453 } 4454 4455 static void 4456 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info, 4457 df_ref def, 4458 int top_flag) 4459 { 4460 bitmap_clear (&seen_in_insn); 4461 4462 for (; def; def = DF_REF_NEXT_LOC (def)) 4463 { 4464 unsigned int dregno = DF_REF_REGNO (def); 4465 if (((!(df->changeable_flags & DF_NO_HARD_REGS)) 4466 || (dregno >= FIRST_PSEUDO_REGISTER)) 4467 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) 4468 { 4469 if (!bitmap_bit_p (&seen_in_insn, dregno)) 4470 { 4471 if (DF_REF_FLAGS (def) 4472 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) 4473 { 4474 bitmap_set_bit (&bb_info->gen, dregno); 4475 bitmap_clear_bit (&bb_info->kill, dregno); 4476 } 4477 else 4478 { 4479 /* When we find a clobber and a regular def, 4480 make sure the regular def wins. */ 4481 bitmap_set_bit (&seen_in_insn, dregno); 4482 bitmap_set_bit (&bb_info->kill, dregno); 4483 bitmap_clear_bit (&bb_info->gen, dregno); 4484 } 4485 } 4486 } 4487 } 4488 } 4489 4490 4491 /* Compute local multiple def info for basic block BB. */ 4492 4493 static void 4494 df_md_bb_local_compute (unsigned int bb_index) 4495 { 4496 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 4497 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); 4498 rtx_insn *insn; 4499 4500 /* Artificials are only hard regs. */ 4501 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 4502 df_md_bb_local_compute_process_def (bb_info, 4503 df_get_artificial_defs (bb_index), 4504 DF_REF_AT_TOP); 4505 4506 FOR_BB_INSNS (bb, insn) 4507 { 4508 unsigned int uid = INSN_UID (insn); 4509 if (!INSN_P (insn)) 4510 continue; 4511 4512 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0); 4513 } 4514 4515 if (!(df->changeable_flags & DF_NO_HARD_REGS)) 4516 df_md_bb_local_compute_process_def (bb_info, 4517 df_get_artificial_defs (bb_index), 4518 0); 4519 } 4520 4521 /* Compute local reaching def info for each basic block within BLOCKS. */ 4522 4523 static void 4524 df_md_local_compute (bitmap all_blocks) 4525 { 4526 unsigned int bb_index, df_bb_index; 4527 bitmap_iterator bi1, bi2; 4528 basic_block bb; 4529 bitmap_head *frontiers; 4530 4531 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack); 4532 4533 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) 4534 { 4535 df_md_bb_local_compute (bb_index); 4536 } 4537 4538 bitmap_clear (&seen_in_insn); 4539 4540 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); 4541 FOR_ALL_BB_FN (bb, cfun) 4542 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack); 4543 4544 compute_dominance_frontiers (frontiers); 4545 4546 /* Add each basic block's kills to the nodes in the frontier of the BB. */ 4547 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) 4548 { 4549 bitmap kill = &df_md_get_bb_info (bb_index)->kill; 4550 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2) 4551 { 4552 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index); 4553 if (bitmap_bit_p (all_blocks, df_bb_index)) 4554 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill, 4555 df_get_live_in (bb)); 4556 } 4557 } 4558 4559 FOR_ALL_BB_FN (bb, cfun) 4560 bitmap_clear (&frontiers[bb->index]); 4561 free (frontiers); 4562 } 4563 4564 4565 /* Reset the global solution for recalculation. */ 4566 4567 static void 4568 df_md_reset (bitmap all_blocks) 4569 { 4570 unsigned int bb_index; 4571 bitmap_iterator bi; 4572 4573 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 4574 { 4575 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); 4576 gcc_assert (bb_info); 4577 bitmap_clear (&bb_info->in); 4578 bitmap_clear (&bb_info->out); 4579 } 4580 } 4581 4582 static bool 4583 df_md_transfer_function (int bb_index) 4584 { 4585 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 4586 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); 4587 bitmap in = &bb_info->in; 4588 bitmap out = &bb_info->out; 4589 bitmap gen = &bb_info->gen; 4590 bitmap kill = &bb_info->kill; 4591 4592 /* We need to use a scratch set here so that the value returned from this 4593 function invocation properly reflects whether the sets changed in a 4594 significant way; i.e. not just because the live set was anded in. */ 4595 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb)); 4596 4597 /* Multiple definitions of a register are not relevant if it is not 4598 live. Thus we trim the result to the places where it is live. */ 4599 bitmap_and_into (in, df_get_live_in (bb)); 4600 4601 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill); 4602 } 4603 4604 /* Initialize the solution bit vectors for problem. */ 4605 4606 static void 4607 df_md_init (bitmap all_blocks) 4608 { 4609 unsigned int bb_index; 4610 bitmap_iterator bi; 4611 4612 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 4613 { 4614 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); 4615 4616 bitmap_copy (&bb_info->in, &bb_info->init); 4617 df_md_transfer_function (bb_index); 4618 } 4619 } 4620 4621 static void 4622 df_md_confluence_0 (basic_block bb) 4623 { 4624 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); 4625 bitmap_copy (&bb_info->in, &bb_info->init); 4626 } 4627 4628 /* In of target gets or of out of source. */ 4629 4630 static bool 4631 df_md_confluence_n (edge e) 4632 { 4633 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in; 4634 bitmap op2 = &df_md_get_bb_info (e->src->index)->out; 4635 4636 if (e->flags & EDGE_FAKE) 4637 return false; 4638 4639 if (e->flags & EDGE_EH) 4640 return bitmap_ior_and_compl_into (op1, op2, 4641 regs_invalidated_by_call_regset); 4642 else 4643 return bitmap_ior_into (op1, op2); 4644 } 4645 4646 /* Free all storage associated with the problem. */ 4647 4648 static void 4649 df_md_free (void) 4650 { 4651 struct df_md_problem_data *problem_data 4652 = (struct df_md_problem_data *) df_md->problem_data; 4653 4654 bitmap_obstack_release (&problem_data->md_bitmaps); 4655 free (problem_data); 4656 df_md->problem_data = NULL; 4657 4658 df_md->block_info_size = 0; 4659 free (df_md->block_info); 4660 df_md->block_info = NULL; 4661 free (df_md); 4662 } 4663 4664 4665 /* Debugging info at top of bb. */ 4666 4667 static void 4668 df_md_top_dump (basic_block bb, FILE *file) 4669 { 4670 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); 4671 if (!bb_info) 4672 return; 4673 4674 fprintf (file, ";; md in \t"); 4675 df_print_regset (file, &bb_info->in); 4676 fprintf (file, ";; md init \t"); 4677 df_print_regset (file, &bb_info->init); 4678 fprintf (file, ";; md gen \t"); 4679 df_print_regset (file, &bb_info->gen); 4680 fprintf (file, ";; md kill \t"); 4681 df_print_regset (file, &bb_info->kill); 4682 } 4683 4684 /* Debugging info at bottom of bb. */ 4685 4686 static void 4687 df_md_bottom_dump (basic_block bb, FILE *file) 4688 { 4689 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); 4690 if (!bb_info) 4691 return; 4692 4693 fprintf (file, ";; md out \t"); 4694 df_print_regset (file, &bb_info->out); 4695 } 4696 4697 static const struct df_problem problem_MD = 4698 { 4699 DF_MD, /* Problem id. */ 4700 DF_FORWARD, /* Direction. */ 4701 df_md_alloc, /* Allocate the problem specific data. */ 4702 df_md_reset, /* Reset global information. */ 4703 df_md_free_bb_info, /* Free basic block info. */ 4704 df_md_local_compute, /* Local compute function. */ 4705 df_md_init, /* Init the solution specific data. */ 4706 df_worklist_dataflow, /* Worklist solver. */ 4707 df_md_confluence_0, /* Confluence operator 0. */ 4708 df_md_confluence_n, /* Confluence operator n. */ 4709 df_md_transfer_function, /* Transfer function. */ 4710 NULL, /* Finalize function. */ 4711 df_md_free, /* Free all of the problem information. */ 4712 df_md_free, /* Remove this problem from the stack of dataflow problems. */ 4713 NULL, /* Debugging. */ 4714 df_md_top_dump, /* Debugging start block. */ 4715 df_md_bottom_dump, /* Debugging end block. */ 4716 NULL, /* Debugging start insn. */ 4717 NULL, /* Debugging end insn. */ 4718 NULL, /* Incremental solution verify start. */ 4719 NULL, /* Incremental solution verify end. */ 4720 NULL, /* Dependent problem. */ 4721 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */ 4722 TV_DF_MD, /* Timing variable. */ 4723 false /* Reset blocks on dropping out of blocks_to_analyze. */ 4724 }; 4725 4726 /* Create a new MD instance and add it to the existing instance 4727 of DF. */ 4728 4729 void 4730 df_md_add_problem (void) 4731 { 4732 df_add_problem (&problem_MD); 4733 } 4734 4735 4736 4737