gcc/df-problems.c

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