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