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