gcc/df-problems.c

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