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