gcc/df-problems.c

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