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