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