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