gcc/df-problems.c

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