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