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