gcc/df-problems.c

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