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