gcc/df-problems.c

   1 /* Standard problems for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
   3    2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
   4    Originally contributed by Michael P. Hayes
   5              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
   6    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
   7              and Kenneth Zadeck (zadeck@naturalbridge.com).
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 3, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING3.  If not see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "insn-config.h"
  32 #include "recog.h"
  33 #include "function.h"
  34 #include "regs.h"
  35 #include "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.  Remove also
2752    REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2753    as the bitmap of currently live registers.  */
2754
2755 static void
2756 df_kill_notes (rtx insn, bitmap live)
2757 {
2758   rtx *pprev = &REG_NOTES (insn);
2759   rtx link = *pprev;
2760
2761   while (link)
2762     {
2763       switch (REG_NOTE_KIND (link))
2764         {
2765         case REG_DEAD:
2766           /* After reg-stack, we need to ignore any unused notes
2767              for the stack registers.  */
2768           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2769             {
2770               pprev = &XEXP (link, 1);
2771               link = *pprev;
2772             }
2773           else
2774             {
2775               rtx next = XEXP (link, 1);
2776 #ifdef REG_DEAD_DEBUGGING
2777               df_print_note ("deleting: ", insn, link);
2778 #endif
2779               free_EXPR_LIST_node (link);
2780               *pprev = link = next;
2781             }
2782           break;
2783
2784         case REG_UNUSED:
2785           /* After reg-stack, we need to ignore any unused notes
2786              for the stack registers.  */
2787           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2788             {
2789               pprev = &XEXP (link, 1);
2790               link = *pprev;
2791             }
2792           else
2793             {
2794               rtx next = XEXP (link, 1);
2795 #ifdef REG_DEAD_DEBUGGING
2796               df_print_note ("deleting: ", insn, link);
2797 #endif
2798               free_EXPR_LIST_node (link);
2799               *pprev = link = next;
2800             }
2801           break;
2802
2803         case REG_EQUAL:
2804         case REG_EQUIV:
2805           {
2806             /* Remove the notes that refer to dead registers.  As we have at most
2807                one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2808                so we need to purge the complete EQ_USES vector when removing
2809                the note using df_notes_rescan.  */
2810             df_ref *use_rec;
2811             bool deleted = false;
2812
2813             for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
2814               {
2815                 df_ref use = *use_rec;
2816                 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
2817                     && DF_REF_LOC (use)
2818                     && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
2819                     && ! bitmap_bit_p (live, DF_REF_REGNO (use))
2820                     && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
2821                   {
2822                     deleted = true;
2823                     break;
2824                   }
2825               }
2826             if (deleted)
2827               {
2828                 rtx next;
2829 #ifdef REG_DEAD_DEBUGGING
2830                 df_print_note ("deleting: ", insn, link);
2831 #endif
2832                 next = XEXP (link, 1);
2833                 free_EXPR_LIST_node (link);
2834                 *pprev = link = next;
2835                 df_notes_rescan (insn);
2836               }
2837             else
2838               {
2839                 pprev = &XEXP (link, 1);
2840                 link = *pprev;
2841               }
2842             break;
2843           }
2844         default:
2845           pprev = &XEXP (link, 1);
2846           link = *pprev;
2847           break;
2848         }
2849     }
2850 }
2851
2852
2853 /* Set a NOTE_TYPE note for REG in INSN.  */
2854
2855 static inline void
2856 df_set_note (enum reg_note note_type, rtx insn, rtx reg)
2857 {
2858   gcc_checking_assert (!DEBUG_INSN_P (insn));
2859   add_reg_note (insn, note_type, reg);
2860 }
2861
2862 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2863    arguments.  Return true if the register value described by MWS's
2864    mw_reg is known to be completely unused, and if mw_reg can therefore
2865    be used in a REG_UNUSED note.  */
2866
2867 static bool
2868 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2869                           bitmap live, bitmap artificial_uses)
2870 {
2871   unsigned int r;
2872
2873   /* If MWS describes a partial reference, create REG_UNUSED notes for
2874      individual hard registers.  */
2875   if (mws->flags & DF_REF_PARTIAL)
2876     return false;
2877
2878   /* Likewise if some part of the register is used.  */
2879   for (r = mws->start_regno; r <= mws->end_regno; r++)
2880     if (bitmap_bit_p (live, r)
2881         || bitmap_bit_p (artificial_uses, r))
2882       return false;
2883
2884   gcc_assert (REG_P (mws->mw_reg));
2885   return true;
2886 }
2887
2888
2889 /* Node of a linked list of uses of dead REGs in debug insns.  */
2890 struct dead_debug_use
2891 {
2892   df_ref use;
2893   struct dead_debug_use *next;
2894 };
2895
2896 /* Linked list of the above, with a bitmap of the REGs in the
2897    list.  */
2898 struct dead_debug
2899 {
2900   struct dead_debug_use *head;
2901   bitmap used;
2902   bitmap to_rescan;
2903 };
2904
2905 static void dead_debug_reset (struct dead_debug *, unsigned int);
2906
2907
2908 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2909    based on the bits in LIVE.  Do not generate notes for registers in
2910    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2911    not generated if the reg is both read and written by the
2912    instruction.
2913 */
2914
2915 static void
2916 df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
2917                             bitmap live, bitmap do_not_gen,
2918                             bitmap artificial_uses,
2919                             struct dead_debug *debug)
2920 {
2921   unsigned int r;
2922
2923 #ifdef REG_DEAD_DEBUGGING
2924   if (dump_file)
2925     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2926              mws->start_regno, mws->end_regno);
2927 #endif
2928
2929   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2930     {
2931       unsigned int regno = mws->start_regno;
2932       df_set_note (REG_UNUSED, insn, mws->mw_reg);
2933       dead_debug_reset (debug, regno);
2934
2935 #ifdef REG_DEAD_DEBUGGING
2936       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2937 #endif
2938       bitmap_set_bit (do_not_gen, regno);
2939       /* Only do this if the value is totally dead.  */
2940     }
2941   else
2942     for (r = mws->start_regno; r <= mws->end_regno; r++)
2943       {
2944         if (!bitmap_bit_p (live, r)
2945             && !bitmap_bit_p (artificial_uses, r))
2946           {
2947             df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
2948             dead_debug_reset (debug, r);
2949 #ifdef REG_DEAD_DEBUGGING
2950             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2951 #endif
2952           }
2953         bitmap_set_bit (do_not_gen, r);
2954       }
2955 }
2956
2957
2958 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2959    arguments.  Return true if the register value described by MWS's
2960    mw_reg is known to be completely dead, and if mw_reg can therefore
2961    be used in a REG_DEAD note.  */
2962
2963 static bool
2964 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2965                         bitmap live, bitmap artificial_uses,
2966                         bitmap do_not_gen)
2967 {
2968   unsigned int r;
2969
2970   /* If MWS describes a partial reference, create REG_DEAD notes for
2971      individual hard registers.  */
2972   if (mws->flags & DF_REF_PARTIAL)
2973     return false;
2974
2975   /* Likewise if some part of the register is not dead.  */
2976   for (r = mws->start_regno; r <= mws->end_regno; r++)
2977     if (bitmap_bit_p (live, r)
2978         || bitmap_bit_p (artificial_uses, r)
2979         || bitmap_bit_p (do_not_gen, r))
2980       return false;
2981
2982   gcc_assert (REG_P (mws->mw_reg));
2983   return true;
2984 }
2985
2986 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2987    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2988    from being set if the instruction both reads and writes the
2989    register.  */
2990
2991 static void
2992 df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
2993                           bitmap live, bitmap do_not_gen,
2994                           bitmap artificial_uses, bool *added_notes_p)
2995 {
2996   unsigned int r;
2997   bool is_debug = *added_notes_p;
2998
2999   *added_notes_p = false;
3000
3001 #ifdef REG_DEAD_DEBUGGING
3002   if (dump_file)
3003     {
3004       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3005                mws->start_regno, mws->end_regno);
3006       df_print_regset (dump_file, do_not_gen);
3007       fprintf (dump_file, "  live =");
3008       df_print_regset (dump_file, live);
3009       fprintf (dump_file, "  artificial uses =");
3010       df_print_regset (dump_file, artificial_uses);
3011     }
3012 #endif
3013
3014   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3015     {
3016       /* Add a dead note for the entire multi word register.  */
3017       if (is_debug)
3018         {
3019           *added_notes_p = true;
3020           return;
3021         }
3022       df_set_note (REG_DEAD, insn, mws->mw_reg);
3023 #ifdef REG_DEAD_DEBUGGING
3024       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3025 #endif
3026     }
3027   else
3028     {
3029       for (r = mws->start_regno; r <= mws->end_regno; r++)
3030         if (!bitmap_bit_p (live, r)
3031             && !bitmap_bit_p (artificial_uses, r)
3032             && !bitmap_bit_p (do_not_gen, r))
3033           {
3034             if (is_debug)
3035               {
3036                 *added_notes_p = true;
3037                 return;
3038               }
3039             df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3040 #ifdef REG_DEAD_DEBUGGING
3041             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3042 #endif
3043           }
3044     }
3045   return;
3046 }
3047
3048
3049 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3050    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3051
3052 static void
3053 df_create_unused_note (rtx insn, df_ref def,
3054                        bitmap live, bitmap artificial_uses,
3055                        struct dead_debug *debug)
3056 {
3057   unsigned int dregno = DF_REF_REGNO (def);
3058
3059 #ifdef REG_DEAD_DEBUGGING
3060   if (dump_file)
3061     {
3062       fprintf (dump_file, "  regular looking at def ");
3063       df_ref_debug (def, dump_file);
3064     }
3065 #endif
3066
3067   if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3068         || bitmap_bit_p (live, dregno)
3069         || bitmap_bit_p (artificial_uses, dregno)
3070         || df_ignore_stack_reg (dregno)))
3071     {
3072       rtx reg = (DF_REF_LOC (def))
3073                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3074       df_set_note (REG_UNUSED, insn, reg);
3075       dead_debug_reset (debug, dregno);
3076 #ifdef REG_DEAD_DEBUGGING
3077       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3078 #endif
3079     }
3080
3081   return;
3082 }
3083
3084
3085 /* Initialize DEBUG to an empty list, and clear USED, if given.  */
3086 static inline void
3087 dead_debug_init (struct dead_debug *debug, bitmap used)
3088 {
3089   debug->head = NULL;
3090   debug->used = used;
3091   debug->to_rescan = NULL;
3092   if (used)
3093     bitmap_clear (used);
3094 }
3095
3096 /* Reset all debug insns with pending uses.  Release the bitmap in it,
3097    unless it is USED.  USED must be the same bitmap passed to
3098    dead_debug_init.  */
3099 static inline void
3100 dead_debug_finish (struct dead_debug *debug, bitmap used)
3101 {
3102   struct dead_debug_use *head;
3103   rtx insn = NULL;
3104
3105   if (debug->used != used)
3106     BITMAP_FREE (debug->used);
3107
3108   while ((head = debug->head))
3109     {
3110       insn = DF_REF_INSN (head->use);
3111       if (!head->next || DF_REF_INSN (head->next->use) != insn)
3112         {
3113           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3114           df_insn_rescan_debug_internal (insn);
3115           if (debug->to_rescan)
3116             bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));
3117         }
3118       debug->head = head->next;
3119       XDELETE (head);
3120     }
3121
3122   if (debug->to_rescan)
3123     {
3124       bitmap_iterator bi;
3125       unsigned int uid;
3126
3127       EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
3128         {
3129           struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
3130           if (insn_info)
3131             df_insn_rescan (insn_info->insn);
3132         }
3133       BITMAP_FREE (debug->to_rescan);
3134     }
3135 }
3136
3137 /* Reset DEBUG_INSNs with pending uses of DREGNO.  */
3138 static void
3139 dead_debug_reset (struct dead_debug *debug, unsigned int dregno)
3140 {
3141   struct dead_debug_use **tailp = &debug->head;
3142   struct dead_debug_use **insnp = &debug->head;
3143   struct dead_debug_use *cur;
3144   rtx insn;
3145
3146   if (!debug->used || !bitmap_clear_bit (debug->used, dregno))
3147     return;
3148
3149   while ((cur = *tailp))
3150     {
3151       if (DF_REF_REGNO (cur->use) == dregno)
3152         {
3153           *tailp = cur->next;
3154           insn = DF_REF_INSN (cur->use);
3155           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3156           if (debug->to_rescan == NULL)
3157             debug->to_rescan = BITMAP_ALLOC (NULL);
3158           bitmap_set_bit (debug->to_rescan, INSN_UID (insn));
3159           XDELETE (cur);
3160           /* If the current use isn't the first one attached to INSN, go back
3161              to this first use.  We assume that the uses attached to an insn
3162              are adjacent.  */
3163           if (tailp != insnp && DF_REF_INSN ((*insnp)->use) == insn)
3164             tailp = insnp;
3165           /* Then remove all the other uses attached to INSN.  */
3166           while ((cur = *tailp) && DF_REF_INSN (cur->use) == insn)
3167             {
3168               *tailp = cur->next;
3169               XDELETE (cur);
3170             }
3171           insnp = tailp;
3172         }
3173       else
3174         {
3175           if (DF_REF_INSN ((*insnp)->use) != DF_REF_INSN (cur->use))
3176             insnp = tailp;
3177           tailp = &(*tailp)->next;
3178         }
3179     }
3180 }
3181
3182 /* Add USE to DEBUG.  It must be a dead reference to UREGNO in a debug
3183    insn.  Create a bitmap for DEBUG as needed.  */
3184 static inline void
3185 dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
3186 {
3187   struct dead_debug_use *newddu = XNEW (struct dead_debug_use);
3188
3189   newddu->use = use;
3190   newddu->next = debug->head;
3191   debug->head = newddu;
3192
3193   if (!debug->used)
3194     debug->used = BITMAP_ALLOC (NULL);
3195
3196   bitmap_set_bit (debug->used, uregno);
3197 }
3198
3199 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3200    before INSN that binds the REG to a debug temp, and replace all
3201    uses of UREGNO in DEBUG with uses of the debug temp.  INSN must be
3202    the insn where UREGNO dies.  */
3203 static inline void
3204 dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
3205                           rtx insn)
3206 {
3207   struct dead_debug_use **tailp = &debug->head;
3208   struct dead_debug_use *cur;
3209   struct dead_debug_use *uses = NULL;
3210   struct dead_debug_use **usesp = &uses;
3211   rtx reg = NULL;
3212   rtx dval;
3213   rtx bind;
3214
3215   if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
3216     return;
3217
3218   /* Move all uses of uregno from debug->head to uses, setting mode to
3219      the widest referenced mode.  */
3220   while ((cur = *tailp))
3221     {
3222       if (DF_REF_REGNO (cur->use) == uregno)
3223         {
3224           *usesp = cur;
3225           usesp = &cur->next;
3226           *tailp = cur->next;
3227           cur->next = NULL;
3228           if (!reg
3229               || (GET_MODE_BITSIZE (GET_MODE (reg))
3230                   < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
3231             reg = *DF_REF_REAL_LOC (cur->use);
3232         }
3233       else
3234         tailp = &(*tailp)->next;
3235     }
3236
3237   /* We may have dangling bits in debug->used for registers that were part
3238      of a multi-register use, one component of which has been reset.  */
3239   if (reg == NULL)
3240     return;
3241
3242   /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL).  */
3243   dval = make_debug_expr_from_rtl (reg);
3244
3245   /* Emit a debug bind insn before the insn in which reg dies.  */
3246   bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
3247                                DEBUG_EXPR_TREE_DECL (dval), reg,
3248                                VAR_INIT_STATUS_INITIALIZED);
3249
3250   bind = emit_debug_insn_before (bind, insn);
3251   df_insn_rescan (bind);
3252
3253   /* Adjust all uses.  */
3254   while ((cur = uses))
3255     {
3256       if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
3257         *DF_REF_REAL_LOC (cur->use) = dval;
3258       else
3259         *DF_REF_REAL_LOC (cur->use)
3260           = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
3261       /* ??? Should we simplify subreg of subreg?  */
3262       if (debug->to_rescan == NULL)
3263         debug->to_rescan = BITMAP_ALLOC (NULL);
3264       bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
3265       uses = cur->next;
3266       XDELETE (cur);
3267     }
3268 }
3269
3270 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3271    info: lifetime, bb, and number of defs and uses for basic block
3272    BB.  The three bitvectors are scratch regs used here.  */
3273
3274 static void
3275 df_note_bb_compute (unsigned int bb_index,
3276                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3277 {
3278   basic_block bb = BASIC_BLOCK (bb_index);
3279   rtx insn;
3280   df_ref *def_rec;
3281   df_ref *use_rec;
3282   struct dead_debug debug;
3283
3284   dead_debug_init (&debug, NULL);
3285
3286   bitmap_copy (live, df_get_live_out (bb));
3287   bitmap_clear (artificial_uses);
3288
3289 #ifdef REG_DEAD_DEBUGGING
3290   if (dump_file)
3291     {
3292       fprintf (dump_file, "live at bottom ");
3293       df_print_regset (dump_file, live);
3294     }
3295 #endif
3296
3297   /* Process the artificial defs and uses at the bottom of the block
3298      to begin processing.  */
3299   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3300     {
3301       df_ref def = *def_rec;
3302 #ifdef REG_DEAD_DEBUGGING
3303       if (dump_file)
3304         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3305 #endif
3306
3307       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3308         bitmap_clear_bit (live, DF_REF_REGNO (def));
3309     }
3310
3311   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3312     {
3313       df_ref use = *use_rec;
3314       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3315         {
3316           unsigned int regno = DF_REF_REGNO (use);
3317           bitmap_set_bit (live, regno);
3318
3319           /* Notes are not generated for any of the artificial registers
3320              at the bottom of the block.  */
3321           bitmap_set_bit (artificial_uses, regno);
3322         }
3323     }
3324
3325 #ifdef REG_DEAD_DEBUGGING
3326   if (dump_file)
3327     {
3328       fprintf (dump_file, "live before artificials out ");
3329       df_print_regset (dump_file, live);
3330     }
3331 #endif
3332
3333   FOR_BB_INSNS_REVERSE (bb, insn)
3334     {
3335       unsigned int uid = INSN_UID (insn);
3336       struct df_mw_hardreg **mws_rec;
3337       int debug_insn;
3338
3339       if (!INSN_P (insn))
3340         continue;
3341
3342       debug_insn = DEBUG_INSN_P (insn);
3343
3344       bitmap_clear (do_not_gen);
3345       df_kill_notes (insn, live);
3346
3347       /* Process the defs.  */
3348       if (CALL_P (insn))
3349         {
3350 #ifdef REG_DEAD_DEBUGGING
3351           if (dump_file)
3352             {
3353               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3354               df_print_regset (dump_file, live);
3355             }
3356 #endif
3357           /* We only care about real sets for calls.  Clobbers cannot
3358              be depended on to really die.  */
3359           mws_rec = DF_INSN_UID_MWS (uid);
3360           while (*mws_rec)
3361             {
3362               struct df_mw_hardreg *mws = *mws_rec;
3363               if ((DF_MWS_REG_DEF_P (mws))
3364                   && !df_ignore_stack_reg (mws->start_regno))
3365               df_set_unused_notes_for_mw (insn,
3366                                           mws, live, do_not_gen,
3367                                           artificial_uses, &debug);
3368               mws_rec++;
3369             }
3370
3371           /* All of the defs except the return value are some sort of
3372              clobber.  This code is for the return.  */
3373           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3374             {
3375               df_ref def = *def_rec;
3376               unsigned int dregno = DF_REF_REGNO (def);
3377               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3378                 {
3379                   df_create_unused_note (insn,
3380                                          def, live, artificial_uses, &debug);
3381                   bitmap_set_bit (do_not_gen, dregno);
3382                 }
3383
3384               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3385                 bitmap_clear_bit (live, dregno);
3386             }
3387         }
3388       else
3389         {
3390           /* Regular insn.  */
3391           mws_rec = DF_INSN_UID_MWS (uid);
3392           while (*mws_rec)
3393             {
3394               struct df_mw_hardreg *mws = *mws_rec;
3395               if (DF_MWS_REG_DEF_P (mws))
3396                 df_set_unused_notes_for_mw (insn,
3397                                             mws, live, do_not_gen,
3398                                             artificial_uses, &debug);
3399               mws_rec++;
3400             }
3401
3402           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3403             {
3404               df_ref def = *def_rec;
3405               unsigned int dregno = DF_REF_REGNO (def);
3406               df_create_unused_note (insn,
3407                                      def, live, artificial_uses, &debug);
3408
3409               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3410                 bitmap_set_bit (do_not_gen, dregno);
3411
3412               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3413                 bitmap_clear_bit (live, dregno);
3414             }
3415         }
3416
3417       /* Process the uses.  */
3418       mws_rec = DF_INSN_UID_MWS (uid);
3419       while (*mws_rec)
3420         {
3421           struct df_mw_hardreg *mws = *mws_rec;
3422           if (DF_MWS_REG_USE_P (mws)
3423               && !df_ignore_stack_reg (mws->start_regno))
3424             {
3425               bool really_add_notes = debug_insn != 0;
3426
3427               df_set_dead_notes_for_mw (insn,
3428                                         mws, live, do_not_gen,
3429                                         artificial_uses,
3430                                         &really_add_notes);
3431
3432               if (really_add_notes)
3433                 debug_insn = -1;
3434             }
3435           mws_rec++;
3436         }
3437
3438       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3439         {
3440           df_ref use = *use_rec;
3441           unsigned int uregno = DF_REF_REGNO (use);
3442
3443 #ifdef REG_DEAD_DEBUGGING
3444           if (dump_file && !debug_insn)
3445             {
3446               fprintf (dump_file, "  regular looking at use ");
3447               df_ref_debug (use, dump_file);
3448             }
3449 #endif
3450           if (!bitmap_bit_p (live, uregno))
3451             {
3452               if (debug_insn)
3453                 {
3454                   if (debug_insn > 0)
3455                     {
3456                       dead_debug_add (&debug, use, uregno);
3457                       continue;
3458                     }
3459                   break;
3460                 }
3461               else
3462                 dead_debug_insert_before (&debug, uregno, insn);
3463
3464               if ( (!(DF_REF_FLAGS (use)
3465                       & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3466                    && (!bitmap_bit_p (do_not_gen, uregno))
3467                    && (!bitmap_bit_p (artificial_uses, uregno))
3468                    && (!df_ignore_stack_reg (uregno)))
3469                 {
3470                   rtx reg = (DF_REF_LOC (use))
3471                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3472                   df_set_note (REG_DEAD, insn, reg);
3473
3474 #ifdef REG_DEAD_DEBUGGING
3475                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3476 #endif
3477                 }
3478               /* This register is now live.  */
3479               bitmap_set_bit (live, uregno);
3480             }
3481         }
3482
3483       if (debug_insn == -1)
3484         {
3485           /* ??? We could probably do better here, replacing dead
3486              registers with their definitions.  */
3487           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3488           df_insn_rescan_debug_internal (insn);
3489         }
3490     }
3491
3492   dead_debug_finish (&debug, NULL);
3493 }
3494
3495
3496 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3497 static void
3498 df_note_compute (bitmap all_blocks)
3499 {
3500   unsigned int bb_index;
3501   bitmap_iterator bi;
3502   bitmap_head live, do_not_gen, artificial_uses;
3503
3504   bitmap_initialize (&live, &df_bitmap_obstack);
3505   bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3506   bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3507
3508 #ifdef REG_DEAD_DEBUGGING
3509   if (dump_file)
3510     print_rtl_with_bb (dump_file, get_insns());
3511 #endif
3512
3513   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3514   {
3515     df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3516   }
3517
3518   bitmap_clear (&live);
3519   bitmap_clear (&do_not_gen);
3520   bitmap_clear (&artificial_uses);
3521 }
3522
3523
3524 /* Free all storage associated with the problem.  */
3525
3526 static void
3527 df_note_free (void)
3528 {
3529   free (df_note);
3530 }
3531
3532
3533 /* All of the information associated every instance of the problem.  */
3534
3535 static struct df_problem problem_NOTE =
3536 {
3537   DF_NOTE,                    /* Problem id.  */
3538   DF_NONE,                    /* Direction.  */
3539   df_note_alloc,              /* Allocate the problem specific data.  */
3540   NULL,                       /* Reset global information.  */
3541   NULL,                       /* Free basic block info.  */
3542   df_note_compute,            /* Local compute function.  */
3543   NULL,                       /* Init the solution specific data.  */
3544   NULL,                       /* Iterative solver.  */
3545   NULL,                       /* Confluence operator 0.  */
3546   NULL,                       /* Confluence operator n.  */
3547   NULL,                       /* Transfer function.  */
3548   NULL,                       /* Finalize function.  */
3549   df_note_free,               /* Free all of the problem information.  */
3550   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3551   NULL,                       /* Debugging.  */
3552   NULL,                       /* Debugging start block.  */
3553   NULL,                       /* Debugging end block.  */
3554   NULL,                       /* Incremental solution verify start.  */
3555   NULL,                       /* Incremental solution verify end.  */
3556   &problem_LR,                /* Dependent problem.  */
3557   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
3558   TV_DF_NOTE,                 /* Timing variable.  */
3559   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3560 };
3561
3562
3563 /* Create a new DATAFLOW instance and add it to an existing instance
3564    of DF.  The returned structure is what is used to get at the
3565    solution.  */
3566
3567 void
3568 df_note_add_problem (void)
3569 {
3570   df_add_problem (&problem_NOTE);
3571 }
3572
3573
3574
3575 \f
3576 /*----------------------------------------------------------------------------
3577    Functions for simulating the effects of single insns.
3578
3579    You can either simulate in the forwards direction, starting from
3580    the top of a block or the backwards direction from the end of the
3581    block.  If you go backwards, defs are examined first to clear bits,
3582    then uses are examined to set bits.  If you go forwards, defs are
3583    examined first to set bits, then REG_DEAD and REG_UNUSED notes
3584    are examined to clear bits.  In either case, the result of examining
3585    a def can be undone (respectively by a use or a REG_UNUSED note).
3586
3587    If you start at the top of the block, use one of DF_LIVE_IN or
3588    DF_LR_IN.  If you start at the bottom of the block use one of
3589    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3590    THEY WILL BE DESTROYED.
3591 ----------------------------------------------------------------------------*/
3592
3593
3594 /* Find the set of DEFs for INSN.  */
3595
3596 void
3597 df_simulate_find_defs (rtx insn, bitmap defs)
3598 {
3599   df_ref *def_rec;
3600   unsigned int uid = INSN_UID (insn);
3601
3602   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3603     {
3604       df_ref def = *def_rec;
3605       bitmap_set_bit (defs, DF_REF_REGNO (def));
3606     }
3607 }
3608
3609 /* Find the set of uses for INSN.  This includes partial defs.  */
3610
3611 static void
3612 df_simulate_find_uses (rtx insn, bitmap uses)
3613 {
3614   df_ref *rec;
3615   unsigned int uid = INSN_UID (insn);
3616
3617   for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
3618     {
3619       df_ref def = *rec;
3620       if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3621         bitmap_set_bit (uses, DF_REF_REGNO (def));
3622     }
3623   for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
3624     {
3625       df_ref use = *rec;
3626       bitmap_set_bit (uses, DF_REF_REGNO (use));
3627     }
3628 }
3629
3630 /* Find the set of real DEFs, which are not clobbers, for INSN.  */
3631
3632 void
3633 df_simulate_find_noclobber_defs (rtx insn, bitmap defs)
3634 {
3635   df_ref *def_rec;
3636   unsigned int uid = INSN_UID (insn);
3637
3638   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3639     {
3640       df_ref def = *def_rec;
3641       if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3642         bitmap_set_bit (defs, DF_REF_REGNO (def));
3643     }
3644 }
3645
3646
3647 /* Simulate the effects of the defs of INSN on LIVE.  */
3648
3649 void
3650 df_simulate_defs (rtx insn, bitmap live)
3651 {
3652   df_ref *def_rec;
3653   unsigned int uid = INSN_UID (insn);
3654
3655   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3656     {
3657       df_ref def = *def_rec;
3658       unsigned int dregno = DF_REF_REGNO (def);
3659
3660       /* If the def is to only part of the reg, it does
3661          not kill the other defs that reach here.  */
3662       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3663         bitmap_clear_bit (live, dregno);
3664     }
3665 }
3666
3667
3668 /* Simulate the effects of the uses of INSN on LIVE.  */
3669
3670 void
3671 df_simulate_uses (rtx insn, bitmap live)
3672 {
3673   df_ref *use_rec;
3674   unsigned int uid = INSN_UID (insn);
3675
3676   if (DEBUG_INSN_P (insn))
3677     return;
3678
3679   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3680     {
3681       df_ref use = *use_rec;
3682       /* Add use to set of uses in this BB.  */
3683       bitmap_set_bit (live, DF_REF_REGNO (use));
3684     }
3685 }
3686
3687
3688 /* Add back the always live regs in BB to LIVE.  */
3689
3690 static inline void
3691 df_simulate_fixup_sets (basic_block bb, bitmap live)
3692 {
3693   /* These regs are considered always live so if they end up dying
3694      because of some def, we need to bring the back again.  */
3695   if (bb_has_eh_pred (bb))
3696     bitmap_ior_into (live, &df->eh_block_artificial_uses);
3697   else
3698     bitmap_ior_into (live, &df->regular_block_artificial_uses);
3699 }
3700
3701
3702 /*----------------------------------------------------------------------------
3703    The following three functions are used only for BACKWARDS scanning:
3704    i.e. they process the defs before the uses.
3705
3706    df_simulate_initialize_backwards should be called first with a
3707    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3708    df_simulate_one_insn_backwards should be called for each insn in
3709    the block, starting with the last one.  Finally,
3710    df_simulate_finalize_backwards can be called to get a new value
3711    of the sets at the top of the block (this is rarely used).
3712    ----------------------------------------------------------------------------*/
3713
3714 /* Apply the artificial uses and defs at the end of BB in a backwards
3715    direction.  */
3716
3717 void
3718 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3719 {
3720   df_ref *def_rec;
3721   df_ref *use_rec;
3722   int bb_index = bb->index;
3723
3724   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3725     {
3726       df_ref def = *def_rec;
3727       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3728         bitmap_clear_bit (live, DF_REF_REGNO (def));
3729     }
3730
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) == 0)
3735         bitmap_set_bit (live, DF_REF_REGNO (use));
3736     }
3737 }
3738
3739
3740 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3741
3742 void
3743 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3744 {
3745   if (!NONDEBUG_INSN_P (insn))
3746     return;
3747
3748   df_simulate_defs (insn, live);
3749   df_simulate_uses (insn, live);
3750   df_simulate_fixup_sets (bb, live);
3751 }
3752
3753
3754 /* Apply the artificial uses and defs at the top of BB in a backwards
3755    direction.  */
3756
3757 void
3758 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3759 {
3760   df_ref *def_rec;
3761 #ifdef EH_USES
3762   df_ref *use_rec;
3763 #endif
3764   int bb_index = bb->index;
3765
3766   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3767     {
3768       df_ref def = *def_rec;
3769       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3770         bitmap_clear_bit (live, DF_REF_REGNO (def));
3771     }
3772
3773 #ifdef EH_USES
3774   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3775     {
3776       df_ref use = *use_rec;
3777       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3778         bitmap_set_bit (live, DF_REF_REGNO (use));
3779     }
3780 #endif
3781 }
3782 /*----------------------------------------------------------------------------
3783    The following three functions are used only for FORWARDS scanning:
3784    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3785    Thus it is important to add the DF_NOTES problem to the stack of
3786    problems computed before using these functions.
3787
3788    df_simulate_initialize_forwards should be called first with a
3789    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3790    df_simulate_one_insn_forwards should be called for each insn in
3791    the block, starting with the first one.
3792    ----------------------------------------------------------------------------*/
3793
3794 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3795    DF_LR_IN for basic block BB, for forward scanning by marking artificial
3796    defs live.  */
3797
3798 void
3799 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3800 {
3801   df_ref *def_rec;
3802   int bb_index = bb->index;
3803
3804   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3805     {
3806       df_ref def = *def_rec;
3807       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3808         bitmap_set_bit (live, DF_REF_REGNO (def));
3809     }
3810 }
3811
3812 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3813
3814 void
3815 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3816 {
3817   rtx link;
3818   if (! INSN_P (insn))
3819     return;
3820
3821   /* Make sure that DF_NOTE really is an active df problem.  */
3822   gcc_assert (df_note);
3823
3824   /* Note that this is the opposite as how the problem is defined, because
3825      in the LR problem defs _kill_ liveness.  However, they do so backwards,
3826      while here the scan is performed forwards!  So, first assume that the
3827      def is live, and if this is not true REG_UNUSED notes will rectify the
3828      situation.  */
3829   df_simulate_find_noclobber_defs (insn, live);
3830
3831   /* Clear all of the registers that go dead.  */
3832   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3833     {
3834       switch (REG_NOTE_KIND (link))
3835         {
3836         case REG_DEAD:
3837         case REG_UNUSED:
3838           {
3839             rtx reg = XEXP (link, 0);
3840             int regno = REGNO (reg);
3841             if (HARD_REGISTER_NUM_P (regno))
3842               bitmap_clear_range (live, regno,
3843                                   hard_regno_nregs[regno][GET_MODE (reg)]);
3844             else
3845               bitmap_clear_bit (live, regno);
3846           }
3847           break;
3848         default:
3849           break;
3850         }
3851     }
3852   df_simulate_fixup_sets (bb, live);
3853 }
3854 \f
3855 /* Used by the next two functions to encode information about the
3856    memory references we found.  */
3857 #define MEMREF_NORMAL 1
3858 #define MEMREF_VOLATILE 2
3859
3860 /* A subroutine of can_move_insns_across_p called through for_each_rtx.
3861    Return either MEMREF_NORMAL or MEMREF_VOLATILE if a memory is found.  */
3862
3863 static int
3864 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3865 {
3866   rtx x = *px;
3867
3868   if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3869     return MEMREF_VOLATILE;
3870
3871   if (!MEM_P (x))
3872     return 0;
3873   if (MEM_VOLATILE_P (x))
3874     return MEMREF_VOLATILE;
3875   if (MEM_READONLY_P (x))
3876     return 0;
3877
3878   return MEMREF_NORMAL;
3879 }
3880
3881 /* A subroutine of can_move_insns_across_p called through note_stores.
3882    DATA points to an integer in which we set either the bit for
3883    MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3884    of either kind.  */
3885
3886 static void
3887 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
3888                     void *data ATTRIBUTE_UNUSED)
3889 {
3890   int *pflags = (int *)data;
3891   if (GET_CODE (x) == SUBREG)
3892     x = XEXP (x, 0);
3893   /* Treat stores to SP as stores to memory, this will prevent problems
3894      when there are references to the stack frame.  */
3895   if (x == stack_pointer_rtx)
3896     *pflags |= MEMREF_VOLATILE;
3897   if (!MEM_P (x))
3898     return;
3899   *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
3900 }
3901
3902 /* Scan BB backwards, using df_simulate functions to keep track of
3903    lifetimes, up to insn POINT.  The result is stored in LIVE.  */
3904
3905 void
3906 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
3907 {
3908   rtx insn;
3909   bitmap_copy (live, df_get_live_out (bb));
3910   df_simulate_initialize_backwards (bb, live);
3911
3912   /* Scan and update life information until we reach the point we're
3913      interested in.  */
3914   for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
3915     df_simulate_one_insn_backwards (bb, insn, live);
3916 }
3917
3918 /* Return true if it is safe to move a group of insns, described by
3919    the range FROM to TO, backwards across another group of insns,
3920    described by ACROSS_FROM to ACROSS_TO.  It is assumed that there
3921    are no insns between ACROSS_TO and FROM, but they may be in
3922    different basic blocks; MERGE_BB is the block from which the
3923    insns will be moved.  The caller must pass in a regset MERGE_LIVE
3924    which specifies the registers live after TO.
3925
3926    This function may be called in one of two cases: either we try to
3927    move identical instructions from all successor blocks into their
3928    predecessor, or we try to move from only one successor block.  If
3929    OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3930    the second case.  It should contain a set of registers live at the
3931    end of ACROSS_TO which must not be clobbered by moving the insns.
3932    In that case, we're also more careful about moving memory references
3933    and trapping insns.
3934
3935    We return false if it is not safe to move the entire group, but it
3936    may still be possible to move a subgroup.  PMOVE_UPTO, if nonnull,
3937    is set to point at the last moveable insn in such a case.  */
3938
3939 bool
3940 can_move_insns_across (rtx from, rtx to, rtx across_from, rtx across_to,
3941                        basic_block merge_bb, regset merge_live,
3942                        regset other_branch_live, rtx *pmove_upto)
3943 {
3944   rtx insn, next, max_to;
3945   bitmap merge_set, merge_use, local_merge_live;
3946   bitmap test_set, test_use;
3947   unsigned i, fail = 0;
3948   bitmap_iterator bi;
3949   int memrefs_in_across = 0;
3950   int mem_sets_in_across = 0;
3951   bool trapping_insns_in_across = false;
3952
3953   if (pmove_upto != NULL)
3954     *pmove_upto = NULL_RTX;
3955
3956   /* Find real bounds, ignoring debug insns.  */
3957   while (!NONDEBUG_INSN_P (from) && from != to)
3958     from = NEXT_INSN (from);
3959   while (!NONDEBUG_INSN_P (to) && from != to)
3960     to = PREV_INSN (to);
3961
3962   for (insn = across_to; ; insn = next)
3963     {
3964       if (CALL_P (insn))
3965         {
3966           if (RTL_CONST_OR_PURE_CALL_P (insn))
3967             /* Pure functions can read from memory.  Const functions can
3968                read from arguments that the ABI has forced onto the stack.
3969                Neither sort of read can be volatile.  */
3970             memrefs_in_across |= MEMREF_NORMAL;
3971           else
3972             {
3973               memrefs_in_across |= MEMREF_VOLATILE;
3974               mem_sets_in_across |= MEMREF_VOLATILE;
3975             }
3976         }
3977       if (NONDEBUG_INSN_P (insn))
3978         {
3979           memrefs_in_across |= for_each_rtx (&PATTERN (insn), find_memory,
3980                                              NULL);
3981           note_stores (PATTERN (insn), find_memory_stores,
3982                        &mem_sets_in_across);
3983           /* This is used just to find sets of the stack pointer.  */
3984           memrefs_in_across |= mem_sets_in_across;
3985           trapping_insns_in_across |= may_trap_p (PATTERN (insn));
3986         }
3987       next = PREV_INSN (insn);
3988       if (insn == across_from)
3989         break;
3990     }
3991
3992   /* Collect:
3993      MERGE_SET = set of registers set in MERGE_BB
3994      MERGE_USE = set of registers used in MERGE_BB and live at its top
3995      MERGE_LIVE = set of registers live at the point inside the MERGE
3996      range that we've reached during scanning
3997      TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3998      TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3999      and live before ACROSS_FROM.  */
4000
4001   merge_set = BITMAP_ALLOC (&reg_obstack);
4002   merge_use = BITMAP_ALLOC (&reg_obstack);
4003   local_merge_live = BITMAP_ALLOC (&reg_obstack);
4004   test_set = BITMAP_ALLOC (&reg_obstack);
4005   test_use = BITMAP_ALLOC (&reg_obstack);
4006
4007   /* Compute the set of registers set and used in the ACROSS range.  */
4008   if (other_branch_live != NULL)
4009     bitmap_copy (test_use, other_branch_live);
4010   df_simulate_initialize_backwards (merge_bb, test_use);
4011   for (insn = across_to; ; insn = next)
4012     {
4013       if (NONDEBUG_INSN_P (insn))
4014         {
4015           df_simulate_find_defs (insn, test_set);
4016           df_simulate_defs (insn, test_use);
4017           df_simulate_uses (insn, test_use);
4018         }
4019       next = PREV_INSN (insn);
4020       if (insn == across_from)
4021         break;
4022     }
4023
4024   /* Compute an upper bound for the amount of insns moved, by finding
4025      the first insn in MERGE that sets a register in TEST_USE, or uses
4026      a register in TEST_SET.  We also check for calls, trapping operations,
4027      and memory references.  */
4028   max_to = NULL_RTX;
4029   for (insn = from; ; insn = next)
4030     {
4031       if (CALL_P (insn))
4032         break;
4033       if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4034         break;
4035       if (NONDEBUG_INSN_P (insn))
4036         {
4037           if (may_trap_or_fault_p (PATTERN (insn))
4038               && (trapping_insns_in_across || other_branch_live != NULL))
4039             break;
4040
4041           /* We cannot move memory stores past each other, or move memory
4042              reads past stores, at least not without tracking them and
4043              calling true_dependence on every pair.
4044
4045              If there is no other branch and no memory references or
4046              sets in the ACROSS range, we can move memory references
4047              freely, even volatile ones.
4048
4049              Otherwise, the rules are as follows: volatile memory
4050              references and stores can't be moved at all, and any type
4051              of memory reference can't be moved if there are volatile
4052              accesses or stores in the ACROSS range.  That leaves
4053              normal reads, which can be moved, as the trapping case is
4054              dealt with elsewhere.  */
4055           if (other_branch_live != NULL || memrefs_in_across != 0)
4056             {
4057               int mem_ref_flags = 0;
4058               int mem_set_flags = 0;
4059               note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
4060               mem_ref_flags = for_each_rtx (&PATTERN (insn), find_memory,
4061                                             NULL);
4062               /* Catch sets of the stack pointer.  */
4063               mem_ref_flags |= mem_set_flags;
4064
4065               if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4066                 break;
4067               if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4068                 break;
4069               if (mem_set_flags != 0
4070                   || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4071                 break;
4072             }
4073           df_simulate_find_uses (insn, merge_use);
4074           /* We're only interested in uses which use a value live at
4075              the top, not one previously set in this block.  */
4076           bitmap_and_compl_into (merge_use, merge_set);
4077           df_simulate_find_defs (insn, merge_set);
4078           if (bitmap_intersect_p (merge_set, test_use)
4079               || bitmap_intersect_p (merge_use, test_set))
4080             break;
4081 #ifdef HAVE_cc0
4082           if (!sets_cc0_p (insn))
4083 #endif
4084             max_to = insn;
4085         }
4086       next = NEXT_INSN (insn);
4087       if (insn == to)
4088         break;
4089     }
4090   if (max_to != to)
4091     fail = 1;
4092
4093   if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4094     goto out;
4095
4096   /* Now, lower this upper bound by also taking into account that
4097      a range of insns moved across ACROSS must not leave a register
4098      live at the end that will be clobbered in ACROSS.  We need to
4099      find a point where TEST_SET & LIVE == 0.
4100
4101      Insns in the MERGE range that set registers which are also set
4102      in the ACROSS range may still be moved as long as we also move
4103      later insns which use the results of the set, and make the
4104      register dead again.  This is verified by the condition stated
4105      above.  We only need to test it for registers that are set in
4106      the moved region.
4107
4108      MERGE_LIVE is provided by the caller and holds live registers after
4109      TO.  */
4110   bitmap_copy (local_merge_live, merge_live);
4111   for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4112     df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4113
4114   /* We're not interested in registers that aren't set in the moved
4115      region at all.  */
4116   bitmap_and_into (local_merge_live, merge_set);
4117   for (;;)
4118     {
4119       if (NONDEBUG_INSN_P (insn))
4120         {
4121           if (!bitmap_intersect_p (test_set, local_merge_live)
4122 #ifdef HAVE_cc0
4123               && !sets_cc0_p (insn)
4124 #endif
4125               )
4126             {
4127               max_to = insn;
4128               break;
4129             }
4130
4131           df_simulate_one_insn_backwards (merge_bb, insn,
4132                                           local_merge_live);
4133         }
4134       if (insn == from)
4135         {
4136           fail = 1;
4137           goto out;
4138         }
4139       insn = PREV_INSN (insn);
4140     }
4141
4142   if (max_to != to)
4143     fail = 1;
4144
4145   if (pmove_upto)
4146     *pmove_upto = max_to;
4147
4148   /* For small register class machines, don't lengthen lifetimes of
4149      hard registers before reload.  */
4150   if (! reload_completed
4151       && targetm.small_register_classes_for_mode_p (VOIDmode))
4152     {
4153       EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4154         {
4155           if (i < FIRST_PSEUDO_REGISTER
4156               && ! fixed_regs[i]
4157               && ! global_regs[i])
4158             fail = 1;
4159         }
4160     }
4161
4162  out:
4163   BITMAP_FREE (merge_set);
4164   BITMAP_FREE (merge_use);
4165   BITMAP_FREE (local_merge_live);
4166   BITMAP_FREE (test_set);
4167   BITMAP_FREE (test_use);
4168
4169   return !fail;
4170 }
4171
4172 \f
4173 /*----------------------------------------------------------------------------
4174    MULTIPLE DEFINITIONS
4175
4176    Find the locations in the function reached by multiple definition sites
4177    for a live pseudo.  In and out bitvectors are built for each basic
4178    block.  They are restricted for efficiency to live registers.
4179
4180    The gen and kill sets for the problem are obvious.  Together they
4181    include all defined registers in a basic block; the gen set includes
4182    registers where a partial or conditional or may-clobber definition is
4183    last in the BB, while the kill set includes registers with a complete
4184    definition coming last.  However, the computation of the dataflow
4185    itself is interesting.
4186
4187    The idea behind it comes from SSA form's iterated dominance frontier
4188    criterion for inserting PHI functions.  Just like in that case, we can use
4189    the dominance frontier to find places where multiple definitions meet;
4190    a register X defined in a basic block BB1 has multiple definitions in
4191    basic blocks in BB1's dominance frontier.
4192
4193    So, the in-set of a basic block BB2 is not just the union of the
4194    out-sets of BB2's predecessors, but includes some more bits that come
4195    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4196    the previous paragraph).  I called this set the init-set of BB2.
4197
4198       (Note: I actually use the kill-set only to build the init-set.
4199       gen bits are anyway propagated from BB1 to BB2 by dataflow).
4200
4201     For example, if you have
4202
4203        BB1 : r10 = 0
4204              r11 = 0
4205              if <...> goto BB2 else goto BB3;
4206
4207        BB2 : r10 = 1
4208              r12 = 1
4209              goto BB3;
4210
4211        BB3 :
4212
4213     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4214     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
4215     not need to iterate the dominance frontier, because we do not insert
4216     anything like PHI functions there!  Instead, dataflow will take care of
4217     propagating the information to BB3's successors.
4218    ---------------------------------------------------------------------------*/
4219
4220 /* Private data used to verify the solution for this problem.  */
4221 struct df_md_problem_data
4222 {
4223   /* An obstack for the bitmaps we need for this problem.  */
4224   bitmap_obstack md_bitmaps;
4225 };
4226
4227 /* Scratch var used by transfer functions.  This is used to do md analysis
4228    only for live registers.  */
4229 static bitmap_head df_md_scratch;
4230
4231
4232 static void
4233 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4234                     void *vbb_info)
4235 {
4236   struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4237   if (bb_info)
4238     {
4239       bitmap_clear (&bb_info->kill);
4240       bitmap_clear (&bb_info->gen);
4241       bitmap_clear (&bb_info->init);
4242       bitmap_clear (&bb_info->in);
4243       bitmap_clear (&bb_info->out);
4244     }
4245 }
4246
4247
4248 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4249    not touched unless the block is new.  */
4250
4251 static void
4252 df_md_alloc (bitmap all_blocks)
4253 {
4254   unsigned int bb_index;
4255   bitmap_iterator bi;
4256   struct df_md_problem_data *problem_data;
4257
4258   df_grow_bb_info (df_md);
4259   if (df_md->problem_data)
4260     problem_data = (struct df_md_problem_data *) df_md->problem_data;
4261   else
4262     {
4263       problem_data = XNEW (struct df_md_problem_data);
4264       df_md->problem_data = problem_data;
4265       bitmap_obstack_initialize (&problem_data->md_bitmaps);
4266     }
4267   bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4268
4269   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4270     {
4271       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4272       /* When bitmaps are already initialized, just clear them.  */
4273       if (bb_info->init.obstack)
4274         {
4275           bitmap_clear (&bb_info->init);
4276           bitmap_clear (&bb_info->gen);
4277           bitmap_clear (&bb_info->kill);
4278           bitmap_clear (&bb_info->in);
4279           bitmap_clear (&bb_info->out);
4280         }
4281       else
4282         {
4283           bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4284           bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4285           bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4286           bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4287           bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4288         }
4289     }
4290
4291   df_md->optional_p = true;
4292 }
4293
4294 /* Add the effect of the top artificial defs of BB to the multiple definitions
4295    bitmap LOCAL_MD.  */
4296
4297 void
4298 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4299 {
4300   int bb_index = bb->index;
4301   df_ref *def_rec;
4302   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4303     {
4304       df_ref def = *def_rec;
4305       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4306         {
4307           unsigned int dregno = DF_REF_REGNO (def);
4308           if (DF_REF_FLAGS (def)
4309               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4310             bitmap_set_bit (local_md, dregno);
4311           else
4312             bitmap_clear_bit (local_md, dregno);
4313         }
4314     }
4315 }
4316
4317
4318 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4319    LOCAL_MD.  */
4320
4321 void
4322 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4323                         bitmap local_md)
4324 {
4325   unsigned uid = INSN_UID (insn);
4326   df_ref *def_rec;
4327
4328   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4329     {
4330       df_ref def = *def_rec;
4331       unsigned int dregno = DF_REF_REGNO (def);
4332       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4333           || (dregno >= FIRST_PSEUDO_REGISTER))
4334         {
4335           if (DF_REF_FLAGS (def)
4336               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4337            bitmap_set_bit (local_md, DF_REF_ID (def));
4338          else
4339            bitmap_clear_bit (local_md, DF_REF_ID (def));
4340         }
4341     }
4342 }
4343
4344 static void
4345 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4346                                     df_ref *def_rec,
4347                                     int top_flag)
4348 {
4349   df_ref def;
4350   bitmap_clear (&seen_in_insn);
4351
4352   while ((def = *def_rec++) != NULL)
4353     {
4354       unsigned int dregno = DF_REF_REGNO (def);
4355       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4356             || (dregno >= FIRST_PSEUDO_REGISTER))
4357           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4358         {
4359           if (!bitmap_bit_p (&seen_in_insn, dregno))
4360             {
4361               if (DF_REF_FLAGS (def)
4362                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4363                 {
4364                   bitmap_set_bit (&bb_info->gen, dregno);
4365                   bitmap_clear_bit (&bb_info->kill, dregno);
4366                 }
4367               else
4368                 {
4369                   /* When we find a clobber and a regular def,
4370                      make sure the regular def wins.  */
4371                   bitmap_set_bit (&seen_in_insn, dregno);
4372                   bitmap_set_bit (&bb_info->kill, dregno);
4373                   bitmap_clear_bit (&bb_info->gen, dregno);
4374                 }
4375             }
4376         }
4377     }
4378 }
4379
4380
4381 /* Compute local multiple def info for basic block BB.  */
4382
4383 static void
4384 df_md_bb_local_compute (unsigned int bb_index)
4385 {
4386   basic_block bb = BASIC_BLOCK (bb_index);
4387   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4388   rtx insn;
4389
4390   /* Artificials are only hard regs.  */
4391   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4392     df_md_bb_local_compute_process_def (bb_info,
4393                                         df_get_artificial_defs (bb_index),
4394                                         DF_REF_AT_TOP);
4395
4396   FOR_BB_INSNS (bb, insn)
4397     {
4398       unsigned int uid = INSN_UID (insn);
4399       if (!INSN_P (insn))
4400         continue;
4401
4402       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4403     }
4404
4405   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4406     df_md_bb_local_compute_process_def (bb_info,
4407                                         df_get_artificial_defs (bb_index),
4408                                         0);
4409 }
4410
4411 /* Compute local reaching def info for each basic block within BLOCKS.  */
4412
4413 static void
4414 df_md_local_compute (bitmap all_blocks)
4415 {
4416   unsigned int bb_index, df_bb_index;
4417   bitmap_iterator bi1, bi2;
4418   basic_block bb;
4419   bitmap_head *frontiers;
4420
4421   bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4422
4423   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4424     {
4425       df_md_bb_local_compute (bb_index);
4426     }
4427
4428   bitmap_clear (&seen_in_insn);
4429
4430   frontiers = XNEWVEC (bitmap_head, last_basic_block);
4431   FOR_ALL_BB (bb)
4432     bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4433
4434   compute_dominance_frontiers (frontiers);
4435
4436   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
4437   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4438     {
4439       bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4440       EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4441         {
4442           basic_block bb = BASIC_BLOCK (df_bb_index);
4443           if (bitmap_bit_p (all_blocks, df_bb_index))
4444             bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4445                                  df_get_live_in (bb));
4446         }
4447     }
4448
4449   FOR_ALL_BB (bb)
4450     bitmap_clear (&frontiers[bb->index]);
4451   free (frontiers);
4452 }
4453
4454
4455 /* Reset the global solution for recalculation.  */
4456
4457 static void
4458 df_md_reset (bitmap all_blocks)
4459 {
4460   unsigned int bb_index;
4461   bitmap_iterator bi;
4462
4463   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4464     {
4465       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4466       gcc_assert (bb_info);
4467       bitmap_clear (&bb_info->in);
4468       bitmap_clear (&bb_info->out);
4469     }
4470 }
4471
4472 static bool
4473 df_md_transfer_function (int bb_index)
4474 {
4475   basic_block bb = BASIC_BLOCK (bb_index);
4476   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4477   bitmap in = &bb_info->in;
4478   bitmap out = &bb_info->out;
4479   bitmap gen = &bb_info->gen;
4480   bitmap kill = &bb_info->kill;
4481
4482   /* We need to use a scratch set here so that the value returned from this
4483      function invocation properly reflects whether the sets changed in a
4484      significant way; i.e. not just because the live set was anded in.  */
4485   bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4486
4487   /* Multiple definitions of a register are not relevant if it is not
4488      live.  Thus we trim the result to the places where it is live.  */
4489   bitmap_and_into (in, df_get_live_in (bb));
4490
4491   return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4492 }
4493
4494 /* Initialize the solution bit vectors for problem.  */
4495
4496 static void
4497 df_md_init (bitmap all_blocks)
4498 {
4499   unsigned int bb_index;
4500   bitmap_iterator bi;
4501
4502   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4503     {
4504       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4505
4506       bitmap_copy (&bb_info->in, &bb_info->init);
4507       df_md_transfer_function (bb_index);
4508     }
4509 }
4510
4511 static void
4512 df_md_confluence_0 (basic_block bb)
4513 {
4514   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4515   bitmap_copy (&bb_info->in, &bb_info->init);
4516 }
4517
4518 /* In of target gets or of out of source.  */
4519
4520 static bool
4521 df_md_confluence_n (edge e)
4522 {
4523   bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4524   bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4525
4526   if (e->flags & EDGE_FAKE)
4527     return false;
4528
4529   if (e->flags & EDGE_EH)
4530     return bitmap_ior_and_compl_into (op1, op2,
4531                                       regs_invalidated_by_call_regset);
4532   else
4533     return bitmap_ior_into (op1, op2);
4534 }
4535
4536 /* Free all storage associated with the problem.  */
4537
4538 static void
4539 df_md_free (void)
4540 {
4541   struct df_md_problem_data *problem_data
4542     = (struct df_md_problem_data *) df_md->problem_data;
4543
4544   bitmap_obstack_release (&problem_data->md_bitmaps);
4545   free (problem_data);
4546   df_md->problem_data = NULL;
4547
4548   df_md->block_info_size = 0;
4549   free (df_md->block_info);
4550   df_md->block_info = NULL;
4551   free (df_md);
4552 }
4553
4554
4555 /* Debugging info at top of bb.  */
4556
4557 static void
4558 df_md_top_dump (basic_block bb, FILE *file)
4559 {
4560   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4561   if (!bb_info)
4562     return;
4563
4564   fprintf (file, ";; md  in  \t");
4565   df_print_regset (file, &bb_info->in);
4566   fprintf (file, ";; md  init  \t");
4567   df_print_regset (file, &bb_info->init);
4568   fprintf (file, ";; md  gen \t");
4569   df_print_regset (file, &bb_info->gen);
4570   fprintf (file, ";; md  kill \t");
4571   df_print_regset (file, &bb_info->kill);
4572 }
4573
4574 /* Debugging info at bottom of bb.  */
4575
4576 static void
4577 df_md_bottom_dump (basic_block bb, FILE *file)
4578 {
4579   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4580   if (!bb_info)
4581     return;
4582
4583   fprintf (file, ";; md  out \t");
4584   df_print_regset (file, &bb_info->out);
4585 }
4586
4587 static struct df_problem problem_MD =
4588 {
4589   DF_MD,                      /* Problem id.  */
4590   DF_FORWARD,                 /* Direction.  */
4591   df_md_alloc,                /* Allocate the problem specific data.  */
4592   df_md_reset,                /* Reset global information.  */
4593   df_md_free_bb_info,         /* Free basic block info.  */
4594   df_md_local_compute,        /* Local compute function.  */
4595   df_md_init,                 /* Init the solution specific data.  */
4596   df_worklist_dataflow,       /* Worklist solver.  */
4597   df_md_confluence_0,         /* Confluence operator 0.  */
4598   df_md_confluence_n,         /* Confluence operator n.  */
4599   df_md_transfer_function,    /* Transfer function.  */
4600   NULL,                       /* Finalize function.  */
4601   df_md_free,                 /* Free all of the problem information.  */
4602   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4603   NULL,                       /* Debugging.  */
4604   df_md_top_dump,             /* Debugging start block.  */
4605   df_md_bottom_dump,          /* Debugging end block.  */
4606   NULL,                       /* Incremental solution verify start.  */
4607   NULL,                       /* Incremental solution verify end.  */
4608   NULL,                       /* Dependent problem.  */
4609   sizeof (struct df_md_bb_info),/* Size of entry of block_info array.  */
4610   TV_DF_MD,                   /* Timing variable.  */
4611   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4612 };
4613
4614 /* Create a new MD instance and add it to the existing instance
4615    of DF.  */
4616
4617 void
4618 df_md_add_problem (void)
4619 {
4620   df_add_problem (&problem_MD);
4621 }
4622
4623
4624