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       fprintf (file, ";;  old in  \t");
1124       df_print_regset (file, &problem_data->in[bb->index]);
1125     }
1126   fprintf (file, ";; lr  use \t");
1127   df_print_regset (file, &bb_info->use);
1128   fprintf (file, ";; lr  def \t");
1129   df_print_regset (file, &bb_info->def);
1130 }
1131
1132
1133 /* Debugging info at bottom of bb.  */
1134
1135 static void
1136 df_lr_bottom_dump (basic_block bb, FILE *file)
1137 {
1138   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1139   struct df_lr_problem_data *problem_data;
1140   if (!bb_info)
1141     return;
1142
1143   fprintf (file, ";; lr  out \t");
1144   df_print_regset (file, &bb_info->out);
1145   if (df_lr->problem_data)
1146     {
1147       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1148       fprintf (file, ";;  old out  \t");
1149       df_print_regset (file, &problem_data->out[bb->index]);
1150     }
1151 }
1152
1153
1154 /* Build the datastructure to verify that the solution to the dataflow
1155    equations is not dirty.  */
1156
1157 static void
1158 df_lr_verify_solution_start (void)
1159 {
1160   basic_block bb;
1161   struct df_lr_problem_data *problem_data;
1162   if (df_lr->solutions_dirty)
1163     return;
1164
1165   /* Set it true so that the solution is recomputed.  */
1166   df_lr->solutions_dirty = true;
1167
1168   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1169   problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1170   problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1171
1172   FOR_ALL_BB (bb)
1173     {
1174       bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1175       bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1176       bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1177       bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1178     }
1179 }
1180
1181
1182 /* Compare the saved datastructure and the new solution to the dataflow
1183    equations.  */
1184
1185 static void
1186 df_lr_verify_solution_end (void)
1187 {
1188   struct df_lr_problem_data *problem_data;
1189   basic_block bb;
1190
1191   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1192
1193   if (!problem_data->out)
1194     return;
1195
1196   if (df_lr->solutions_dirty)
1197     /* Do not check if the solution is still dirty.  See the comment
1198        in df_lr_finalize for details.  */
1199     df_lr->solutions_dirty = false;
1200   else
1201     FOR_ALL_BB (bb)
1202       {
1203         if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1204             || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1205           {
1206             /*df_dump (stderr);*/
1207             gcc_unreachable ();
1208           }
1209       }
1210
1211   /* Cannot delete them immediately because you may want to dump them
1212      if the comparison fails.  */
1213   FOR_ALL_BB (bb)
1214     {
1215       bitmap_clear (&problem_data->in[bb->index]);
1216       bitmap_clear (&problem_data->out[bb->index]);
1217     }
1218
1219   free (problem_data->in);
1220   free (problem_data->out);
1221   problem_data->in = NULL;
1222   problem_data->out = NULL;
1223 }
1224
1225
1226 /* All of the information associated with every instance of the problem.  */
1227
1228 static struct df_problem problem_LR =
1229 {
1230   DF_LR,                      /* Problem id.  */
1231   DF_BACKWARD,                /* Direction.  */
1232   df_lr_alloc,                /* Allocate the problem specific data.  */
1233   df_lr_reset,                /* Reset global information.  */
1234   df_lr_free_bb_info,         /* Free basic block info.  */
1235   df_lr_local_compute,        /* Local compute function.  */
1236   df_lr_init,                 /* Init the solution specific data.  */
1237   df_worklist_dataflow,       /* Worklist solver.  */
1238   df_lr_confluence_0,         /* Confluence operator 0.  */
1239   df_lr_confluence_n,         /* Confluence operator n.  */
1240   df_lr_transfer_function,    /* Transfer function.  */
1241   df_lr_finalize,             /* Finalize function.  */
1242   df_lr_free,                 /* Free all of the problem information.  */
1243   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1244   NULL,                       /* Debugging.  */
1245   df_lr_top_dump,             /* Debugging start block.  */
1246   df_lr_bottom_dump,          /* Debugging end block.  */
1247   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1248   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1249   NULL,                       /* Dependent problem.  */
1250   TV_DF_LR,                   /* Timing variable.  */
1251   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1252 };
1253
1254
1255 /* Create a new DATAFLOW instance and add it to an existing instance
1256    of DF.  The returned structure is what is used to get at the
1257    solution.  */
1258
1259 void
1260 df_lr_add_problem (void)
1261 {
1262   df_add_problem (&problem_LR);
1263   /* These will be initialized when df_scan_blocks processes each
1264      block.  */
1265   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1266 }
1267
1268
1269 /* Verify that all of the lr related info is consistent and
1270    correct.  */
1271
1272 void
1273 df_lr_verify_transfer_functions (void)
1274 {
1275   basic_block bb;
1276   bitmap_head saved_def;
1277   bitmap_head saved_use;
1278   bitmap_head all_blocks;
1279
1280   if (!df)
1281     return;
1282
1283   bitmap_initialize (&saved_def, &bitmap_default_obstack);
1284   bitmap_initialize (&saved_use, &bitmap_default_obstack);
1285   bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1286
1287   FOR_ALL_BB (bb)
1288     {
1289       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1290       bitmap_set_bit (&all_blocks, bb->index);
1291
1292       if (bb_info)
1293         {
1294           /* Make a copy of the transfer functions and then compute
1295              new ones to see if the transfer functions have
1296              changed.  */
1297           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1298                              bb->index))
1299             {
1300               bitmap_copy (&saved_def, &bb_info->def);
1301               bitmap_copy (&saved_use, &bb_info->use);
1302               bitmap_clear (&bb_info->def);
1303               bitmap_clear (&bb_info->use);
1304
1305               df_lr_bb_local_compute (bb->index);
1306               gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1307               gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1308             }
1309         }
1310       else
1311         {
1312           /* If we do not have basic block info, the block must be in
1313              the list of dirty blocks or else some one has added a
1314              block behind our backs. */
1315           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1316                                     bb->index));
1317         }
1318       /* Make sure no one created a block without following
1319          procedures.  */
1320       gcc_assert (df_scan_get_bb_info (bb->index));
1321     }
1322
1323   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1324   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1325                                          &all_blocks));
1326
1327   bitmap_clear (&saved_def);
1328   bitmap_clear (&saved_use);
1329   bitmap_clear (&all_blocks);
1330 }
1331
1332
1333 \f
1334 /*----------------------------------------------------------------------------
1335    LIVE AND MUST-INITIALIZED REGISTERS.
1336
1337    This problem first computes the IN and OUT bitvectors for the
1338    must-initialized registers problems, which is a forward problem.
1339    It gives the set of registers for which we MUST have an available
1340    definition on any path from the entry block to the entry/exit of
1341    a basic block.  Sets generate a definition, while clobbers kill
1342    a definition.
1343
1344    In and out bitvectors are built for each basic block and are indexed by
1345    regnum (see df.h for details).  In and out bitvectors in struct
1346    df_live_bb_info actually refers to the must-initialized problem;
1347
1348    Then, the in and out sets for the LIVE problem itself are computed.
1349    These are the logical AND of the IN and OUT sets from the LR problem
1350    and the must-initialized problem.
1351 ----------------------------------------------------------------------------*/
1352
1353 /* Private data used to verify the solution for this problem.  */
1354 struct df_live_problem_data
1355 {
1356   bitmap_head *in;
1357   bitmap_head *out;
1358 };
1359
1360 /* Scratch var used by transfer functions.  This is used to implement
1361    an optimization to reduce the amount of space used to compute the
1362    combined lr and live analysis.  */
1363 static bitmap df_live_scratch;
1364
1365 /* Set basic block info.  */
1366
1367 static void
1368 df_live_set_bb_info (unsigned int index,
1369                    struct df_live_bb_info *bb_info)
1370 {
1371   gcc_assert (df_live);
1372   gcc_assert (index < df_live->block_info_size);
1373   df_live->block_info[index] = bb_info;
1374 }
1375
1376
1377 /* Free basic block info.  */
1378
1379 static void
1380 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1381                     void *vbb_info)
1382 {
1383   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1384   if (bb_info)
1385     {
1386       bitmap_clear (&bb_info->gen);
1387       bitmap_clear (&bb_info->kill);
1388       bitmap_clear (&bb_info->in);
1389       bitmap_clear (&bb_info->out);
1390       pool_free (df_live->block_pool, bb_info);
1391     }
1392 }
1393
1394
1395 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1396    not touched unless the block is new.  */
1397
1398 static void
1399 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1400 {
1401   unsigned int bb_index;
1402   bitmap_iterator bi;
1403
1404   if (!df_live->block_pool)
1405     df_live->block_pool = create_alloc_pool ("df_live_block pool",
1406                                            sizeof (struct df_live_bb_info), 100);
1407   if (!df_live_scratch)
1408     df_live_scratch = BITMAP_ALLOC (NULL);
1409
1410   df_grow_bb_info (df_live);
1411
1412   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1413     {
1414       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1415       if (bb_info)
1416         {
1417           bitmap_clear (&bb_info->kill);
1418           bitmap_clear (&bb_info->gen);
1419         }
1420       else
1421         {
1422           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1423           df_live_set_bb_info (bb_index, bb_info);
1424           bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
1425           bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
1426           bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
1427           bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
1428         }
1429     }
1430   df_live->optional_p = (optimize <= 1);
1431 }
1432
1433
1434 /* Reset the global solution for recalculation.  */
1435
1436 static void
1437 df_live_reset (bitmap all_blocks)
1438 {
1439   unsigned int bb_index;
1440   bitmap_iterator bi;
1441
1442   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1443     {
1444       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1445       gcc_assert (bb_info);
1446       bitmap_clear (&bb_info->in);
1447       bitmap_clear (&bb_info->out);
1448     }
1449 }
1450
1451
1452 /* Compute local uninitialized register info for basic block BB.  */
1453
1454 static void
1455 df_live_bb_local_compute (unsigned int bb_index)
1456 {
1457   basic_block bb = BASIC_BLOCK (bb_index);
1458   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1459   rtx insn;
1460   df_ref *def_rec;
1461   int luid = 0;
1462
1463   FOR_BB_INSNS (bb, insn)
1464     {
1465       unsigned int uid = INSN_UID (insn);
1466       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1467
1468       /* Inserting labels does not always trigger the incremental
1469          rescanning.  */
1470       if (!insn_info)
1471         {
1472           gcc_assert (!INSN_P (insn));
1473           insn_info = df_insn_create_insn_record (insn);
1474         }
1475
1476       DF_INSN_INFO_LUID (insn_info) = luid;
1477       if (!INSN_P (insn))
1478         continue;
1479
1480       luid++;
1481       for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
1482         {
1483           df_ref def = *def_rec;
1484           unsigned int regno = DF_REF_REGNO (def);
1485
1486           if (DF_REF_FLAGS_IS_SET (def,
1487                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1488             /* All partial or conditional def
1489                seen are included in the gen set. */
1490             bitmap_set_bit (&bb_info->gen, regno);
1491           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1492             /* Only must clobbers for the entire reg destroy the
1493                value.  */
1494             bitmap_set_bit (&bb_info->kill, regno);
1495           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1496             bitmap_set_bit (&bb_info->gen, regno);
1497         }
1498     }
1499
1500   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1501     {
1502       df_ref def = *def_rec;
1503       bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1504     }
1505 }
1506
1507
1508 /* Compute local uninitialized register info.  */
1509
1510 static void
1511 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1512 {
1513   unsigned int bb_index;
1514   bitmap_iterator bi;
1515
1516   df_grow_insn_info ();
1517
1518   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1519                             0, bb_index, bi)
1520     {
1521       df_live_bb_local_compute (bb_index);
1522     }
1523
1524   bitmap_clear (df_live->out_of_date_transfer_functions);
1525 }
1526
1527
1528 /* Initialize the solution vectors.  */
1529
1530 static void
1531 df_live_init (bitmap all_blocks)
1532 {
1533   unsigned int bb_index;
1534   bitmap_iterator bi;
1535
1536   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1537     {
1538       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1539       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1540
1541       /* No register may reach a location where it is not used.  Thus
1542          we trim the rr result to the places where it is used.  */
1543       bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1544       bitmap_clear (&bb_info->in);
1545     }
1546 }
1547
1548 /* Forward confluence function that ignores fake edges.  */
1549
1550 static void
1551 df_live_confluence_n (edge e)
1552 {
1553   bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1554   bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1555
1556   if (e->flags & EDGE_FAKE)
1557     return;
1558
1559   bitmap_ior_into (op1, op2);
1560 }
1561
1562
1563 /* Transfer function for the forwards must-initialized problem.  */
1564
1565 static bool
1566 df_live_transfer_function (int bb_index)
1567 {
1568   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1569   struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1570   bitmap in = &bb_info->in;
1571   bitmap out = &bb_info->out;
1572   bitmap gen = &bb_info->gen;
1573   bitmap kill = &bb_info->kill;
1574
1575   /* We need to use a scratch set here so that the value returned from this
1576      function invocation properly reflects whether the sets changed in a
1577      significant way; i.e. not just because the lr set was anded in.  */
1578   bitmap_and (df_live_scratch, gen, &bb_lr_info->out);
1579   /* No register may reach a location where it is not used.  Thus
1580      we trim the rr result to the places where it is used.  */
1581   bitmap_and_into (in, &bb_lr_info->in);
1582
1583   return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1584 }
1585
1586
1587 /* And the LR info with the must-initialized registers, to produce the LIVE info.  */
1588
1589 static void
1590 df_live_finalize (bitmap all_blocks)
1591 {
1592
1593   if (df_live->solutions_dirty)
1594     {
1595       bitmap_iterator bi;
1596       unsigned int bb_index;
1597
1598       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1599         {
1600           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1601           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1602
1603           /* No register may reach a location where it is not used.  Thus
1604              we trim the rr result to the places where it is used.  */
1605           bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1606           bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1607         }
1608
1609       df_live->solutions_dirty = false;
1610     }
1611 }
1612
1613
1614 /* Free all storage associated with the problem.  */
1615
1616 static void
1617 df_live_free (void)
1618 {
1619   if (df_live->block_info)
1620     {
1621       unsigned int i;
1622
1623       for (i = 0; i < df_live->block_info_size; i++)
1624         {
1625           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1626           if (bb_info)
1627             {
1628               bitmap_clear (&bb_info->gen);
1629               bitmap_clear (&bb_info->kill);
1630               bitmap_clear (&bb_info->in);
1631               bitmap_clear (&bb_info->out);
1632             }
1633         }
1634
1635       free_alloc_pool (df_live->block_pool);
1636       df_live->block_info_size = 0;
1637       free (df_live->block_info);
1638
1639       if (df_live_scratch)
1640         BITMAP_FREE (df_live_scratch);
1641     }
1642   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1643   free (df_live);
1644 }
1645
1646
1647 /* Debugging info at top of bb.  */
1648
1649 static void
1650 df_live_top_dump (basic_block bb, FILE *file)
1651 {
1652   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1653   struct df_live_problem_data *problem_data;
1654
1655   if (!bb_info)
1656     return;
1657
1658   fprintf (file, ";; live  in  \t");
1659   df_print_regset (file, &bb_info->in);
1660   if (df_live->problem_data)
1661     {
1662       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1663       fprintf (file, ";;  old in  \t");
1664       df_print_regset (file, &problem_data->in[bb->index]);
1665     }
1666   fprintf (file, ";; live  gen \t");
1667   df_print_regset (file, &bb_info->gen);
1668   fprintf (file, ";; live  kill\t");
1669   df_print_regset (file, &bb_info->kill);
1670 }
1671
1672
1673 /* Debugging info at bottom of bb.  */
1674
1675 static void
1676 df_live_bottom_dump (basic_block bb, FILE *file)
1677 {
1678   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1679   struct df_live_problem_data *problem_data;
1680
1681   if (!bb_info)
1682     return;
1683
1684   fprintf (file, ";; live  out \t");
1685   df_print_regset (file, &bb_info->out);
1686   if (df_live->problem_data)
1687     {
1688       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1689       fprintf (file, ";;  old out  \t");
1690       df_print_regset (file, &problem_data->out[bb->index]);
1691     }
1692 }
1693
1694
1695 /* Build the datastructure to verify that the solution to the dataflow
1696    equations is not dirty.  */
1697
1698 static void
1699 df_live_verify_solution_start (void)
1700 {
1701   basic_block bb;
1702   struct df_live_problem_data *problem_data;
1703   if (df_live->solutions_dirty)
1704     {
1705       df_live->problem_data = NULL;
1706       return;
1707     }
1708
1709   /* Set it true so that the solution is recomputed.  */
1710   df_live->solutions_dirty = true;
1711
1712   problem_data = XNEW (struct df_live_problem_data);
1713   df_live->problem_data = problem_data;
1714   problem_data->in = XNEWVEC (bitmap_head, last_basic_block);
1715   problem_data->out = XNEWVEC (bitmap_head, last_basic_block);
1716
1717   FOR_ALL_BB (bb)
1718     {
1719       bitmap_initialize (&problem_data->in[bb->index], &bitmap_default_obstack);
1720       bitmap_initialize (&problem_data->out[bb->index], &bitmap_default_obstack);
1721       bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1722       bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1723     }
1724 }
1725
1726
1727 /* Compare the saved datastructure and the new solution to the dataflow
1728    equations.  */
1729
1730 static void
1731 df_live_verify_solution_end (void)
1732 {
1733   struct df_live_problem_data *problem_data;
1734   basic_block bb;
1735
1736   if (df_live->problem_data == NULL)
1737     return;
1738
1739   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1740
1741   FOR_ALL_BB (bb)
1742     {
1743       if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1744           || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1745         {
1746           /*df_dump (stderr);*/
1747           gcc_unreachable ();
1748         }
1749     }
1750
1751   /* Cannot delete them immediately because you may want to dump them
1752      if the comparison fails.  */
1753   FOR_ALL_BB (bb)
1754     {
1755       bitmap_clear (&problem_data->in[bb->index]);
1756       bitmap_clear (&problem_data->out[bb->index]);
1757     }
1758
1759   free (problem_data->in);
1760   free (problem_data->out);
1761   free (problem_data);
1762   df_live->problem_data = NULL;
1763 }
1764
1765
1766 /* All of the information associated with every instance of the problem.  */
1767
1768 static struct df_problem problem_LIVE =
1769 {
1770   DF_LIVE,                      /* Problem id.  */
1771   DF_FORWARD,                   /* Direction.  */
1772   df_live_alloc,                /* Allocate the problem specific data.  */
1773   df_live_reset,                /* Reset global information.  */
1774   df_live_free_bb_info,         /* Free basic block info.  */
1775   df_live_local_compute,        /* Local compute function.  */
1776   df_live_init,                 /* Init the solution specific data.  */
1777   df_worklist_dataflow,         /* Worklist solver.  */
1778   NULL,                         /* Confluence operator 0.  */
1779   df_live_confluence_n,         /* Confluence operator n.  */
1780   df_live_transfer_function,    /* Transfer function.  */
1781   df_live_finalize,             /* Finalize function.  */
1782   df_live_free,                 /* Free all of the problem information.  */
1783   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1784   NULL,                         /* Debugging.  */
1785   df_live_top_dump,             /* Debugging start block.  */
1786   df_live_bottom_dump,          /* Debugging end block.  */
1787   df_live_verify_solution_start,/* Incremental solution verify start.  */
1788   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1789   &problem_LR,                  /* Dependent problem.  */
1790   TV_DF_LIVE,                   /* Timing variable.  */
1791   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1792 };
1793
1794
1795 /* Create a new DATAFLOW instance and add it to an existing instance
1796    of DF.  The returned structure is what is used to get at the
1797    solution.  */
1798
1799 void
1800 df_live_add_problem (void)
1801 {
1802   df_add_problem (&problem_LIVE);
1803   /* These will be initialized when df_scan_blocks processes each
1804      block.  */
1805   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1806 }
1807
1808
1809 /* Set all of the blocks as dirty.  This needs to be done if this
1810    problem is added after all of the insns have been scanned.  */
1811
1812 void
1813 df_live_set_all_dirty (void)
1814 {
1815   basic_block bb;
1816   FOR_ALL_BB (bb)
1817     bitmap_set_bit (df_live->out_of_date_transfer_functions,
1818                     bb->index);
1819 }
1820
1821
1822 /* Verify that all of the lr related info is consistent and
1823    correct.  */
1824
1825 void
1826 df_live_verify_transfer_functions (void)
1827 {
1828   basic_block bb;
1829   bitmap_head saved_gen;
1830   bitmap_head saved_kill;
1831   bitmap_head all_blocks;
1832
1833   if (!df)
1834     return;
1835
1836   bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1837   bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1838   bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1839
1840   df_grow_insn_info ();
1841
1842   FOR_ALL_BB (bb)
1843     {
1844       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1845       bitmap_set_bit (&all_blocks, bb->index);
1846
1847       if (bb_info)
1848         {
1849           /* Make a copy of the transfer functions and then compute
1850              new ones to see if the transfer functions have
1851              changed.  */
1852           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1853                              bb->index))
1854             {
1855               bitmap_copy (&saved_gen, &bb_info->gen);
1856               bitmap_copy (&saved_kill, &bb_info->kill);
1857               bitmap_clear (&bb_info->gen);
1858               bitmap_clear (&bb_info->kill);
1859
1860               df_live_bb_local_compute (bb->index);
1861               gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1862               gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1863             }
1864         }
1865       else
1866         {
1867           /* If we do not have basic block info, the block must be in
1868              the list of dirty blocks or else some one has added a
1869              block behind our backs. */
1870           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1871                                     bb->index));
1872         }
1873       /* Make sure no one created a block without following
1874          procedures.  */
1875       gcc_assert (df_scan_get_bb_info (bb->index));
1876     }
1877
1878   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1879   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1880                                          &all_blocks));
1881   bitmap_clear (&saved_gen);
1882   bitmap_clear (&saved_kill);
1883   bitmap_clear (&all_blocks);
1884 }
1885 \f
1886 /*----------------------------------------------------------------------------
1887    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1888
1889    Link either the defs to the uses and / or the uses to the defs.
1890
1891    These problems are set up like the other dataflow problems so that
1892    they nicely fit into the framework.  They are much simpler and only
1893    involve a single traversal of instructions and an examination of
1894    the reaching defs information (the dependent problem).
1895 ----------------------------------------------------------------------------*/
1896
1897 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1898
1899 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1900
1901 struct df_link *
1902 df_chain_create (df_ref src, df_ref dst)
1903 {
1904   struct df_link *head = DF_REF_CHAIN (src);
1905   struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1906
1907   DF_REF_CHAIN (src) = link;
1908   link->next = head;
1909   link->ref = dst;
1910   return link;
1911 }
1912
1913
1914 /* Delete any du or ud chains that start at REF and point to
1915    TARGET.  */
1916 static void
1917 df_chain_unlink_1 (df_ref ref, df_ref target)
1918 {
1919   struct df_link *chain = DF_REF_CHAIN (ref);
1920   struct df_link *prev = NULL;
1921
1922   while (chain)
1923     {
1924       if (chain->ref == target)
1925         {
1926           if (prev)
1927             prev->next = chain->next;
1928           else
1929             DF_REF_CHAIN (ref) = chain->next;
1930           pool_free (df_chain->block_pool, chain);
1931           return;
1932         }
1933       prev = chain;
1934       chain = chain->next;
1935     }
1936 }
1937
1938
1939 /* Delete a du or ud chain that leave or point to REF.  */
1940
1941 void
1942 df_chain_unlink (df_ref ref)
1943 {
1944   struct df_link *chain = DF_REF_CHAIN (ref);
1945   while (chain)
1946     {
1947       struct df_link *next = chain->next;
1948       /* Delete the other side if it exists.  */
1949       df_chain_unlink_1 (chain->ref, ref);
1950       pool_free (df_chain->block_pool, chain);
1951       chain = next;
1952     }
1953   DF_REF_CHAIN (ref) = NULL;
1954 }
1955
1956
1957 /* Copy the du or ud chain starting at FROM_REF and attach it to
1958    TO_REF.  */
1959
1960 void
1961 df_chain_copy (df_ref to_ref,
1962                struct df_link *from_ref)
1963 {
1964   while (from_ref)
1965     {
1966       df_chain_create (to_ref, from_ref->ref);
1967       from_ref = from_ref->next;
1968     }
1969 }
1970
1971
1972 /* Remove this problem from the stack of dataflow problems.  */
1973
1974 static void
1975 df_chain_remove_problem (void)
1976 {
1977   bitmap_iterator bi;
1978   unsigned int bb_index;
1979
1980   /* Wholesale destruction of the old chains.  */
1981   if (df_chain->block_pool)
1982     free_alloc_pool (df_chain->block_pool);
1983
1984   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1985     {
1986       rtx insn;
1987       df_ref *def_rec;
1988       df_ref *use_rec;
1989       basic_block bb = BASIC_BLOCK (bb_index);
1990
1991       if (df_chain_problem_p (DF_DU_CHAIN))
1992         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1993           DF_REF_CHAIN (*def_rec) = NULL;
1994       if (df_chain_problem_p (DF_UD_CHAIN))
1995         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1996           DF_REF_CHAIN (*use_rec) = NULL;
1997
1998       FOR_BB_INSNS (bb, insn)
1999         {
2000           unsigned int uid = INSN_UID (insn);
2001
2002           if (INSN_P (insn))
2003             {
2004               if (df_chain_problem_p (DF_DU_CHAIN))
2005                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2006                   DF_REF_CHAIN (*def_rec) = NULL;
2007               if (df_chain_problem_p (DF_UD_CHAIN))
2008                 {
2009                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2010                     DF_REF_CHAIN (*use_rec) = NULL;
2011                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
2012                     DF_REF_CHAIN (*use_rec) = NULL;
2013                 }
2014             }
2015         }
2016     }
2017
2018   bitmap_clear (df_chain->out_of_date_transfer_functions);
2019   df_chain->block_pool = NULL;
2020 }
2021
2022
2023 /* Remove the chain problem completely.  */
2024
2025 static void
2026 df_chain_fully_remove_problem (void)
2027 {
2028   df_chain_remove_problem ();
2029   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2030   free (df_chain);
2031 }
2032
2033
2034 /* Create def-use or use-def chains.  */
2035
2036 static void
2037 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2038 {
2039   df_chain_remove_problem ();
2040   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2041                                          sizeof (struct df_link), 50);
2042   df_chain->optional_p = true;
2043 }
2044
2045
2046 /* Reset all of the chains when the set of basic blocks changes.  */
2047
2048 static void
2049 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2050 {
2051   df_chain_remove_problem ();
2052 }
2053
2054
2055 /* Create the chains for a list of USEs.  */
2056
2057 static void
2058 df_chain_create_bb_process_use (bitmap local_rd,
2059                                 df_ref *use_rec,
2060                                 int top_flag)
2061 {
2062   bitmap_iterator bi;
2063   unsigned int def_index;
2064
2065   while (*use_rec)
2066     {
2067       df_ref use = *use_rec;
2068       unsigned int uregno = DF_REF_REGNO (use);
2069       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2070           || (uregno >= FIRST_PSEUDO_REGISTER))
2071         {
2072           /* Do not want to go through this for an uninitialized var.  */
2073           int count = DF_DEFS_COUNT (uregno);
2074           if (count)
2075             {
2076               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2077                 {
2078                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2079                   unsigned int last_index = first_index + count - 1;
2080
2081                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2082                     {
2083                       df_ref def;
2084                       if (def_index > last_index)
2085                         break;
2086
2087                       def = DF_DEFS_GET (def_index);
2088                       if (df_chain_problem_p (DF_DU_CHAIN))
2089                         df_chain_create (def, use);
2090                       if (df_chain_problem_p (DF_UD_CHAIN))
2091                         df_chain_create (use, def);
2092                     }
2093                 }
2094             }
2095         }
2096
2097       use_rec++;
2098     }
2099 }
2100
2101
2102 /* Create chains from reaching defs bitmaps for basic block BB.  */
2103
2104 static void
2105 df_chain_create_bb (unsigned int bb_index)
2106 {
2107   basic_block bb = BASIC_BLOCK (bb_index);
2108   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2109   rtx insn;
2110   bitmap_head cpy;
2111
2112   bitmap_initialize (&cpy, &bitmap_default_obstack);
2113   bitmap_copy (&cpy, &bb_info->in);
2114   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2115
2116   /* Since we are going forwards, process the artificial uses first
2117      then the artificial defs second.  */
2118
2119 #ifdef EH_USES
2120   /* Create the chains for the artificial uses from the EH_USES at the
2121      beginning of the block.  */
2122
2123   /* Artificials are only hard regs.  */
2124   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2125     df_chain_create_bb_process_use (&cpy,
2126                                     df_get_artificial_uses (bb->index),
2127                                     DF_REF_AT_TOP);
2128 #endif
2129
2130   df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2131
2132   /* Process the regular instructions next.  */
2133   FOR_BB_INSNS (bb, insn)
2134     if (INSN_P (insn))
2135       {
2136         unsigned int uid = INSN_UID (insn);
2137
2138         /* First scan the uses and link them up with the defs that remain
2139            in the cpy vector.  */
2140         df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2141         if (df->changeable_flags & DF_EQ_NOTES)
2142           df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2143
2144         /* Since we are going forwards, process the defs second.  */
2145         df_rd_simulate_one_insn (bb, insn, &cpy);
2146       }
2147
2148   /* Create the chains for the artificial uses of the hard registers
2149      at the end of the block.  */
2150   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2151     df_chain_create_bb_process_use (&cpy,
2152                                     df_get_artificial_uses (bb->index),
2153                                     0);
2154
2155   bitmap_clear (&cpy);
2156 }
2157
2158 /* Create def-use chains from reaching use bitmaps for basic blocks
2159    in BLOCKS.  */
2160
2161 static void
2162 df_chain_finalize (bitmap all_blocks)
2163 {
2164   unsigned int bb_index;
2165   bitmap_iterator bi;
2166
2167   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2168     {
2169       df_chain_create_bb (bb_index);
2170     }
2171 }
2172
2173
2174 /* Free all storage associated with the problem.  */
2175
2176 static void
2177 df_chain_free (void)
2178 {
2179   free_alloc_pool (df_chain->block_pool);
2180   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2181   free (df_chain);
2182 }
2183
2184
2185 /* Debugging info.  */
2186
2187 static void
2188 df_chain_top_dump (basic_block bb, FILE *file)
2189 {
2190   if (df_chain_problem_p (DF_DU_CHAIN))
2191     {
2192       rtx insn;
2193       df_ref *def_rec = df_get_artificial_defs (bb->index);
2194       if (*def_rec)
2195         {
2196
2197           fprintf (file, ";;  DU chains for artificial defs\n");
2198           while (*def_rec)
2199             {
2200               df_ref def = *def_rec;
2201               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2202               df_chain_dump (DF_REF_CHAIN (def), file);
2203               fprintf (file, "\n");
2204               def_rec++;
2205             }
2206         }
2207
2208       FOR_BB_INSNS (bb, insn)
2209         {
2210           if (INSN_P (insn))
2211             {
2212               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2213               def_rec = DF_INSN_INFO_DEFS (insn_info);
2214               if (*def_rec)
2215                 {
2216                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2217                            DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2218
2219                   while (*def_rec)
2220                     {
2221                       df_ref def = *def_rec;
2222                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2223                       if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2224                         fprintf (file, "read/write ");
2225                       df_chain_dump (DF_REF_CHAIN (def), file);
2226                       fprintf (file, "\n");
2227                       def_rec++;
2228                     }
2229                 }
2230             }
2231         }
2232     }
2233 }
2234
2235
2236 static void
2237 df_chain_bottom_dump (basic_block bb, FILE *file)
2238 {
2239   if (df_chain_problem_p (DF_UD_CHAIN))
2240     {
2241       rtx insn;
2242       df_ref *use_rec = df_get_artificial_uses (bb->index);
2243
2244       if (*use_rec)
2245         {
2246           fprintf (file, ";;  UD chains for artificial uses\n");
2247           while (*use_rec)
2248             {
2249               df_ref use = *use_rec;
2250               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2251               df_chain_dump (DF_REF_CHAIN (use), file);
2252               fprintf (file, "\n");
2253               use_rec++;
2254             }
2255         }
2256
2257       FOR_BB_INSNS (bb, insn)
2258         {
2259           if (INSN_P (insn))
2260             {
2261               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2262               df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
2263               use_rec = DF_INSN_INFO_USES (insn_info);
2264               if (*use_rec || *eq_use_rec)
2265                 {
2266                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2267                            DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2268
2269                   while (*use_rec)
2270                     {
2271                       df_ref use = *use_rec;
2272                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2273                       if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2274                         fprintf (file, "read/write ");
2275                       df_chain_dump (DF_REF_CHAIN (use), file);
2276                       fprintf (file, "\n");
2277                       use_rec++;
2278                     }
2279                   while (*eq_use_rec)
2280                     {
2281                       df_ref use = *eq_use_rec;
2282                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2283                       df_chain_dump (DF_REF_CHAIN (use), file);
2284                       fprintf (file, "\n");
2285                       eq_use_rec++;
2286                     }
2287                 }
2288             }
2289         }
2290     }
2291 }
2292
2293
2294 static struct df_problem problem_CHAIN =
2295 {
2296   DF_CHAIN,                   /* Problem id.  */
2297   DF_NONE,                    /* Direction.  */
2298   df_chain_alloc,             /* Allocate the problem specific data.  */
2299   df_chain_reset,             /* Reset global information.  */
2300   NULL,                       /* Free basic block info.  */
2301   NULL,                       /* Local compute function.  */
2302   NULL,                       /* Init the solution specific data.  */
2303   NULL,                       /* Iterative solver.  */
2304   NULL,                       /* Confluence operator 0.  */
2305   NULL,                       /* Confluence operator n.  */
2306   NULL,                       /* Transfer function.  */
2307   df_chain_finalize,          /* Finalize function.  */
2308   df_chain_free,              /* Free all of the problem information.  */
2309   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2310   NULL,                       /* Debugging.  */
2311   df_chain_top_dump,          /* Debugging start block.  */
2312   df_chain_bottom_dump,       /* Debugging end block.  */
2313   NULL,                       /* Incremental solution verify start.  */
2314   NULL,                       /* Incremental solution verify end.  */
2315   &problem_RD,                /* Dependent problem.  */
2316   TV_DF_CHAIN,                /* Timing variable.  */
2317   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2318 };
2319
2320
2321 /* Create a new DATAFLOW instance and add it to an existing instance
2322    of DF.  The returned structure is what is used to get at the
2323    solution.  */
2324
2325 void
2326 df_chain_add_problem (unsigned int chain_flags)
2327 {
2328   df_add_problem (&problem_CHAIN);
2329   df_chain->local_flags = chain_flags;
2330   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2331 }
2332
2333 #undef df_chain_problem_p
2334
2335 \f
2336 /*----------------------------------------------------------------------------
2337    BYTE LEVEL LIVE REGISTERS
2338
2339    Find the locations in the function where any use of a pseudo can
2340    reach in the backwards direction.  In and out bitvectors are built
2341    for each basic block.  There are two mapping functions,
2342    df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2343    used to map regnos into bit vector positions.
2344
2345    This problem differs from the regular df_lr function in the way
2346    that subregs, *_extracts and strict_low_parts are handled. In lr
2347    these are consider partial kills, here, the exact set of bytes is
2348    modeled.  Note that any reg that has none of these operations is
2349    only modeled with a single bit since all operations access the
2350    entire register.
2351
2352    This problem is more brittle that the regular lr.  It currently can
2353    be used in dce incrementally, but cannot be used in an environment
2354    where insns are created or modified.  The problem is that the
2355    mapping of regnos to bitmap positions is relatively compact, in
2356    that if a pseudo does not do any of the byte wise operations, only
2357    one slot is allocated, rather than a slot for each byte.  If insn
2358    are created, where a subreg is used for a reg that had no subregs,
2359    the mapping would be wrong.  Likewise, there are no checks to see
2360    that new pseudos have been added.  These issues could be addressed
2361    by adding a problem specific flag to not use the compact mapping,
2362    if there was a need to do so.
2363
2364    ----------------------------------------------------------------------------*/
2365
2366 /* Private data used to verify the solution for this problem.  */
2367 struct df_byte_lr_problem_data
2368 {
2369   /* Expanded versions of bitvectors used in lr.  */
2370   bitmap_head invalidated_by_call;
2371   bitmap_head hardware_regs_used;
2372
2373   /* Indexed by regno, this is true if there are subregs, extracts or
2374      strict_low_parts for this regno.  */
2375   bitmap_head needs_expansion;
2376
2377   /* The start position and len for each regno in the various bit
2378      vectors.  */
2379   unsigned int* regno_start;
2380   unsigned int* regno_len;
2381   /* An obstack for the bitmaps we need for this problem.  */
2382   bitmap_obstack byte_lr_bitmaps;
2383 };
2384
2385
2386 /* Get the starting location for REGNO in the df_byte_lr bitmaps.  */
2387
2388 int
2389 df_byte_lr_get_regno_start (unsigned int regno)
2390 {
2391   struct df_byte_lr_problem_data *problem_data
2392     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2393   return problem_data->regno_start[regno];
2394 }
2395
2396
2397 /* Get the len for REGNO in the df_byte_lr bitmaps.  */
2398
2399 int
2400 df_byte_lr_get_regno_len (unsigned int regno)
2401 {
2402   struct df_byte_lr_problem_data *problem_data
2403     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2404   return problem_data->regno_len[regno];
2405 }
2406
2407
2408 /* Set basic block info.  */
2409
2410 static void
2411 df_byte_lr_set_bb_info (unsigned int index,
2412                         struct df_byte_lr_bb_info *bb_info)
2413 {
2414   gcc_assert (df_byte_lr);
2415   gcc_assert (index < df_byte_lr->block_info_size);
2416   df_byte_lr->block_info[index] = bb_info;
2417 }
2418
2419
2420 /* Free basic block info.  */
2421
2422 static void
2423 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2424                          void *vbb_info)
2425 {
2426   struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2427   if (bb_info)
2428     {
2429       bitmap_clear (&bb_info->use);
2430       bitmap_clear (&bb_info->def);
2431       bitmap_clear (&bb_info->in);
2432       bitmap_clear (&bb_info->out);
2433       pool_free (df_byte_lr->block_pool, bb_info);
2434     }
2435 }
2436
2437
2438 /* Check all of the refs in REF_REC to see if any of them are
2439    extracts, subregs or strict_low_parts.  */
2440
2441 static void
2442 df_byte_lr_check_regs (df_ref *ref_rec)
2443 {
2444   struct df_byte_lr_problem_data *problem_data
2445     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2446
2447   for (; *ref_rec; ref_rec++)
2448     {
2449       df_ref ref = *ref_rec;
2450       if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2451                                | DF_REF_ZERO_EXTRACT
2452                                | DF_REF_STRICT_LOW_PART)
2453           || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2454         bitmap_set_bit (&problem_data->needs_expansion, DF_REF_REGNO (ref));
2455     }
2456 }
2457
2458
2459 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2460    regno_start and regno_len.  */
2461
2462 static void
2463 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2464 {
2465   struct df_byte_lr_problem_data *problem_data
2466     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2467   bitmap_iterator bi;
2468   unsigned int i;
2469
2470   bitmap_clear (dest);
2471   EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2472     {
2473       bitmap_set_range (dest, problem_data->regno_start[i],
2474                         problem_data->regno_len[i]);
2475     }
2476 }
2477
2478
2479 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2480    not touched unless the block is new.  */
2481
2482 static void
2483 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2484 {
2485   unsigned int bb_index;
2486   bitmap_iterator bi;
2487   basic_block bb;
2488   unsigned int regno;
2489   unsigned int index = 0;
2490   unsigned int max_reg = max_reg_num();
2491   struct df_byte_lr_problem_data *problem_data
2492     = XNEW (struct df_byte_lr_problem_data);
2493
2494   df_byte_lr->problem_data = problem_data;
2495
2496   if (!df_byte_lr->block_pool)
2497     df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2498                                            sizeof (struct df_byte_lr_bb_info), 50);
2499
2500   df_grow_bb_info (df_byte_lr);
2501
2502   /* Create the mapping from regnos to slots. This does not change
2503      unless the problem is destroyed and recreated.  In particular, if
2504      we end up deleting the only insn that used a subreg, we do not
2505      want to redo the mapping because this would invalidate everything
2506      else.  */
2507
2508   bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2509   problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2510   problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2511   bitmap_initialize (&problem_data->hardware_regs_used,
2512                      &problem_data->byte_lr_bitmaps);
2513   bitmap_initialize (&problem_data->invalidated_by_call,
2514                      &problem_data->byte_lr_bitmaps);
2515   bitmap_initialize (&problem_data->needs_expansion,
2516                      &problem_data->byte_lr_bitmaps);
2517
2518   /* Discover which regno's use subregs, extracts or
2519      strict_low_parts.  */
2520   FOR_EACH_BB (bb)
2521     {
2522       rtx insn;
2523       FOR_BB_INSNS (bb, insn)
2524         {
2525           if (INSN_P (insn))
2526             {
2527               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2528               df_byte_lr_check_regs (DF_INSN_INFO_DEFS (insn_info));
2529               df_byte_lr_check_regs (DF_INSN_INFO_USES (insn_info));
2530             }
2531         }
2532       bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2533     }
2534
2535   bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2536   bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2537
2538   /* Allocate the slots for each regno.  */
2539   for (regno = 0; regno < max_reg; regno++)
2540     {
2541       int len;
2542       problem_data->regno_start[regno] = index;
2543       if (bitmap_bit_p (&problem_data->needs_expansion, regno))
2544         len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2545       else
2546         len = 1;
2547
2548       problem_data->regno_len[regno] = len;
2549       index += len;
2550     }
2551
2552   df_byte_lr_expand_bitmap (&problem_data->hardware_regs_used,
2553                             &df->hardware_regs_used);
2554   df_byte_lr_expand_bitmap (&problem_data->invalidated_by_call,
2555                             regs_invalidated_by_call_regset);
2556
2557   EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2558     {
2559       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2560       if (bb_info)
2561         {
2562           bitmap_clear (&bb_info->def);
2563           bitmap_clear (&bb_info->use);
2564         }
2565       else
2566         {
2567           bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2568           df_byte_lr_set_bb_info (bb_index, bb_info);
2569           bitmap_initialize (&bb_info->use, &problem_data->byte_lr_bitmaps);
2570           bitmap_initialize (&bb_info->def, &problem_data->byte_lr_bitmaps);
2571           bitmap_initialize (&bb_info->in, &problem_data->byte_lr_bitmaps);
2572           bitmap_initialize (&bb_info->out, &problem_data->byte_lr_bitmaps);
2573         }
2574     }
2575
2576   df_byte_lr->optional_p = true;
2577 }
2578
2579
2580 /* Reset the global solution for recalculation.  */
2581
2582 static void
2583 df_byte_lr_reset (bitmap all_blocks)
2584 {
2585   unsigned int bb_index;
2586   bitmap_iterator bi;
2587
2588   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2589     {
2590       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2591       gcc_assert (bb_info);
2592       bitmap_clear (&bb_info->in);
2593       bitmap_clear (&bb_info->out);
2594     }
2595 }
2596
2597
2598 /* Compute local live register info for basic block BB.  */
2599
2600 static void
2601 df_byte_lr_bb_local_compute (unsigned int bb_index)
2602 {
2603   struct df_byte_lr_problem_data *problem_data
2604     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2605   basic_block bb = BASIC_BLOCK (bb_index);
2606   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2607   rtx insn;
2608   df_ref *def_rec;
2609   df_ref *use_rec;
2610
2611   /* Process the registers set in an exception handler.  */
2612   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2613     {
2614       df_ref def = *def_rec;
2615       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2616         {
2617           unsigned int dregno = DF_REF_REGNO (def);
2618           unsigned int start = problem_data->regno_start[dregno];
2619           unsigned int len = problem_data->regno_len[dregno];
2620           bitmap_set_range (&bb_info->def, start, len);
2621           bitmap_clear_range (&bb_info->use, start, len);
2622         }
2623     }
2624
2625   /* Process the hardware registers that are always live.  */
2626   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2627     {
2628       df_ref use = *use_rec;
2629       /* Add use to set of uses in this BB.  */
2630       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2631         {
2632           unsigned int uregno = DF_REF_REGNO (use);
2633           unsigned int start = problem_data->regno_start[uregno];
2634           unsigned int len = problem_data->regno_len[uregno];
2635           bitmap_set_range (&bb_info->use, start, len);
2636         }
2637     }
2638
2639   FOR_BB_INSNS_REVERSE (bb, insn)
2640     {
2641       unsigned int uid = INSN_UID (insn);
2642
2643       if (!INSN_P (insn))
2644         continue;
2645
2646       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2647         {
2648           df_ref def = *def_rec;
2649           /* If the def is to only part of the reg, it does
2650              not kill the other defs that reach here.  */
2651           if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2652             {
2653               unsigned int dregno = DF_REF_REGNO (def);
2654               unsigned int start = problem_data->regno_start[dregno];
2655               unsigned int len = problem_data->regno_len[dregno];
2656               unsigned int sb;
2657               unsigned int lb;
2658               if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2659                 {
2660                   start += sb;
2661                   len = lb - sb;
2662                 }
2663               if (len)
2664                 {
2665                   bitmap_set_range (&bb_info->def, start, len);
2666                   bitmap_clear_range (&bb_info->use, start, len);
2667                 }
2668             }
2669         }
2670
2671       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2672         {
2673           df_ref use = *use_rec;
2674           unsigned int uregno = DF_REF_REGNO (use);
2675           unsigned int start = problem_data->regno_start[uregno];
2676           unsigned int len = problem_data->regno_len[uregno];
2677           unsigned int sb;
2678           unsigned int lb;
2679           if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2680             {
2681               start += sb;
2682               len = lb - sb;
2683             }
2684           /* Add use to set of uses in this BB.  */
2685           if (len)
2686             bitmap_set_range (&bb_info->use, start, len);
2687         }
2688     }
2689
2690   /* Process the registers set in an exception handler or the hard
2691      frame pointer if this block is the target of a non local
2692      goto.  */
2693   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2694     {
2695       df_ref def = *def_rec;
2696       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2697         {
2698           unsigned int dregno = DF_REF_REGNO (def);
2699           unsigned int start = problem_data->regno_start[dregno];
2700           unsigned int len = problem_data->regno_len[dregno];
2701           bitmap_set_range (&bb_info->def, start, len);
2702           bitmap_clear_range (&bb_info->use, start, len);
2703         }
2704     }
2705
2706 #ifdef EH_USES
2707   /* Process the uses that are live into an exception handler.  */
2708   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2709     {
2710       df_ref use = *use_rec;
2711       /* Add use to set of uses in this BB.  */
2712       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2713         {
2714           unsigned int uregno = DF_REF_REGNO (use);
2715           unsigned int start = problem_data->regno_start[uregno];
2716           unsigned int len = problem_data->regno_len[uregno];
2717           bitmap_set_range (&bb_info->use, start, len);
2718         }
2719     }
2720 #endif
2721 }
2722
2723
2724 /* Compute local live register info for each basic block within BLOCKS.  */
2725
2726 static void
2727 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2728 {
2729   unsigned int bb_index;
2730   bitmap_iterator bi;
2731
2732   EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2733     {
2734       if (bb_index == EXIT_BLOCK)
2735         {
2736           /* The exit block is special for this problem and its bits are
2737              computed from thin air.  */
2738           struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2739           df_byte_lr_expand_bitmap (&bb_info->use, df->exit_block_uses);
2740         }
2741       else
2742         df_byte_lr_bb_local_compute (bb_index);
2743     }
2744
2745   bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2746 }
2747
2748
2749 /* Initialize the solution vectors.  */
2750
2751 static void
2752 df_byte_lr_init (bitmap all_blocks)
2753 {
2754   unsigned int bb_index;
2755   bitmap_iterator bi;
2756
2757   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2758     {
2759       struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2760       bitmap_copy (&bb_info->in, &bb_info->use);
2761       bitmap_clear (&bb_info->out);
2762     }
2763 }
2764
2765
2766 /* Confluence function that processes infinite loops.  This might be a
2767    noreturn function that throws.  And even if it isn't, getting the
2768    unwind info right helps debugging.  */
2769 static void
2770 df_byte_lr_confluence_0 (basic_block bb)
2771 {
2772   struct df_byte_lr_problem_data *problem_data
2773     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2774   bitmap op1 = &df_byte_lr_get_bb_info (bb->index)->out;
2775   if (bb != EXIT_BLOCK_PTR)
2776     bitmap_copy (op1, &problem_data->hardware_regs_used);
2777 }
2778
2779
2780 /* Confluence function that ignores fake edges.  */
2781
2782 static void
2783 df_byte_lr_confluence_n (edge e)
2784 {
2785   struct df_byte_lr_problem_data *problem_data
2786     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2787   bitmap op1 = &df_byte_lr_get_bb_info (e->src->index)->out;
2788   bitmap op2 = &df_byte_lr_get_bb_info (e->dest->index)->in;
2789
2790   /* Call-clobbered registers die across exception and call edges.  */
2791   /* ??? Abnormal call edges ignored for the moment, as this gets
2792      confused by sibling call edges, which crashes reg-stack.  */
2793   if (e->flags & EDGE_EH)
2794     bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
2795   else
2796     bitmap_ior_into (op1, op2);
2797
2798   bitmap_ior_into (op1, &problem_data->hardware_regs_used);
2799 }
2800
2801
2802 /* Transfer function.  */
2803
2804 static bool
2805 df_byte_lr_transfer_function (int bb_index)
2806 {
2807   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2808   bitmap in = &bb_info->in;
2809   bitmap out = &bb_info->out;
2810   bitmap use = &bb_info->use;
2811   bitmap def = &bb_info->def;
2812
2813   return bitmap_ior_and_compl (in, use, out, def);
2814 }
2815
2816
2817 /* Free all storage associated with the problem.  */
2818
2819 static void
2820 df_byte_lr_free (void)
2821 {
2822   struct df_byte_lr_problem_data *problem_data
2823     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2824
2825
2826   if (df_byte_lr->block_info)
2827     {
2828       free_alloc_pool (df_byte_lr->block_pool);
2829       df_byte_lr->block_info_size = 0;
2830       free (df_byte_lr->block_info);
2831     }
2832
2833   BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2834   bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2835   free (problem_data->regno_start);
2836   free (problem_data->regno_len);
2837   free (problem_data);
2838   free (df_byte_lr);
2839 }
2840
2841
2842 /* Debugging info at top of bb.  */
2843
2844 static void
2845 df_byte_lr_top_dump (basic_block bb, FILE *file)
2846 {
2847   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2848   if (!bb_info)
2849     return;
2850
2851   fprintf (file, ";; blr  in  \t");
2852   df_print_byte_regset (file, &bb_info->in);
2853   fprintf (file, ";; blr  use \t");
2854   df_print_byte_regset (file, &bb_info->use);
2855   fprintf (file, ";; blr  def \t");
2856   df_print_byte_regset (file, &bb_info->def);
2857 }
2858
2859
2860 /* Debugging info at bottom of bb.  */
2861
2862 static void
2863 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2864 {
2865   struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2866   if (!bb_info)
2867     return;
2868
2869   fprintf (file, ";; blr  out \t");
2870   df_print_byte_regset (file, &bb_info->out);
2871 }
2872
2873
2874 /* All of the information associated with every instance of the problem.  */
2875
2876 static struct df_problem problem_BYTE_LR =
2877 {
2878   DF_BYTE_LR,                      /* Problem id.  */
2879   DF_BACKWARD,                     /* Direction.  */
2880   df_byte_lr_alloc,                /* Allocate the problem specific data.  */
2881   df_byte_lr_reset,                /* Reset global information.  */
2882   df_byte_lr_free_bb_info,         /* Free basic block info.  */
2883   df_byte_lr_local_compute,        /* Local compute function.  */
2884   df_byte_lr_init,                 /* Init the solution specific data.  */
2885   df_worklist_dataflow,            /* Worklist solver.  */
2886   df_byte_lr_confluence_0,         /* Confluence operator 0.  */
2887   df_byte_lr_confluence_n,         /* Confluence operator n.  */
2888   df_byte_lr_transfer_function,    /* Transfer function.  */
2889   NULL,                            /* Finalize function.  */
2890   df_byte_lr_free,                 /* Free all of the problem information.  */
2891   df_byte_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
2892   NULL,                            /* Debugging.  */
2893   df_byte_lr_top_dump,             /* Debugging start block.  */
2894   df_byte_lr_bottom_dump,          /* Debugging end block.  */
2895   NULL,                            /* Incremental solution verify start.  */
2896   NULL,                            /* Incremental solution verify end.  */
2897   NULL,                            /* Dependent problem.  */
2898   TV_DF_BYTE_LR,                   /* Timing variable.  */
2899   false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
2900 };
2901
2902
2903 /* Create a new DATAFLOW instance and add it to an existing instance
2904    of DF.  The returned structure is what is used to get at the
2905    solution.  */
2906
2907 void
2908 df_byte_lr_add_problem (void)
2909 {
2910   df_add_problem (&problem_BYTE_LR);
2911   /* These will be initialized when df_scan_blocks processes each
2912      block.  */
2913   df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2914 }
2915
2916
2917 /* Simulate the effects of the defs of INSN on LIVE.  */
2918
2919 void
2920 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2921 {
2922   struct df_byte_lr_problem_data *problem_data
2923     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2924   df_ref *def_rec;
2925   unsigned int uid = INSN_UID (insn);
2926
2927   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2928     {
2929       df_ref def = *def_rec;
2930
2931       /* If the def is to only part of the reg, it does
2932          not kill the other defs that reach here.  */
2933       if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2934         {
2935           unsigned int dregno = DF_REF_REGNO (def);
2936           unsigned int start = problem_data->regno_start[dregno];
2937           unsigned int len = problem_data->regno_len[dregno];
2938           unsigned int sb;
2939           unsigned int lb;
2940           if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2941             {
2942               start += sb;
2943               len = lb - sb;
2944             }
2945
2946           if (len)
2947             bitmap_clear_range (live, start, len);
2948         }
2949     }
2950 }
2951
2952
2953 /* Simulate the effects of the uses of INSN on LIVE.  */
2954
2955 void
2956 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2957 {
2958   struct df_byte_lr_problem_data *problem_data
2959     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2960   df_ref *use_rec;
2961   unsigned int uid = INSN_UID (insn);
2962
2963   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2964     {
2965       df_ref use = *use_rec;
2966       unsigned int uregno = DF_REF_REGNO (use);
2967       unsigned int start = problem_data->regno_start[uregno];
2968       unsigned int len = problem_data->regno_len[uregno];
2969       unsigned int sb;
2970       unsigned int lb;
2971
2972       if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2973         {
2974           start += sb;
2975           len = lb - sb;
2976         }
2977
2978       /* Add use to set of uses in this BB.  */
2979       if (len)
2980         bitmap_set_range (live, start, len);
2981     }
2982 }
2983
2984
2985 /* Apply the artificial uses and defs at the top of BB in a forwards
2986    direction.  */
2987
2988 void
2989 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2990 {
2991   struct df_byte_lr_problem_data *problem_data
2992     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2993   df_ref *def_rec;
2994 #ifdef EH_USES
2995   df_ref *use_rec;
2996 #endif
2997   int bb_index = bb->index;
2998
2999 #ifdef EH_USES
3000   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3001     {
3002       df_ref use = *use_rec;
3003       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3004         {
3005           unsigned int uregno = DF_REF_REGNO (use);
3006           unsigned int start = problem_data->regno_start[uregno];
3007           unsigned int len = problem_data->regno_len[uregno];
3008           bitmap_set_range (live, start, len);
3009         }
3010     }
3011 #endif
3012
3013   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3014     {
3015       df_ref def = *def_rec;
3016       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3017         {
3018           unsigned int dregno = DF_REF_REGNO (def);
3019           unsigned int start = problem_data->regno_start[dregno];
3020           unsigned int len = problem_data->regno_len[dregno];
3021           bitmap_clear_range (live, start, len);
3022         }
3023     }
3024 }
3025
3026
3027 /* Apply the artificial uses and defs at the end of BB in a backwards
3028    direction.  */
3029
3030 void
3031 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3032 {
3033   struct df_byte_lr_problem_data *problem_data
3034     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3035   df_ref *def_rec;
3036   df_ref *use_rec;
3037   int bb_index = bb->index;
3038
3039   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3040     {
3041       df_ref def = *def_rec;
3042       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3043         {
3044           unsigned int dregno = DF_REF_REGNO (def);
3045           unsigned int start = problem_data->regno_start[dregno];
3046           unsigned int len = problem_data->regno_len[dregno];
3047           bitmap_clear_range (live, start, len);
3048         }
3049     }
3050
3051   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3052     {
3053       df_ref use = *use_rec;
3054       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3055         {
3056           unsigned int uregno = DF_REF_REGNO (use);
3057           unsigned int start = problem_data->regno_start[uregno];
3058           unsigned int len = problem_data->regno_len[uregno];
3059           bitmap_set_range (live, start, len);
3060         }
3061     }
3062 }
3063
3064
3065 \f
3066 /*----------------------------------------------------------------------------
3067    This problem computes REG_DEAD and REG_UNUSED notes.
3068    ----------------------------------------------------------------------------*/
3069
3070 static void
3071 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3072 {
3073   df_note->optional_p = true;
3074 }
3075
3076 #ifdef REG_DEAD_DEBUGGING
3077 static void
3078 df_print_note (const char *prefix, rtx insn, rtx note)
3079 {
3080   if (dump_file)
3081     {
3082       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3083       print_rtl (dump_file, note);
3084       fprintf (dump_file, "\n");
3085     }
3086 }
3087 #endif
3088
3089
3090 /* After reg-stack, the x86 floating point stack regs are difficult to
3091    analyze because of all of the pushes, pops and rotations.  Thus, we
3092    just leave the notes alone. */
3093
3094 #ifdef STACK_REGS
3095 static inline bool
3096 df_ignore_stack_reg (int regno)
3097 {
3098   return regstack_completed
3099     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3100 }
3101 #else
3102 static inline bool
3103 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3104 {
3105   return false;
3106 }
3107 #endif
3108
3109
3110 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3111    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
3112
3113 static void
3114 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3115 {
3116   rtx *pprev = &REG_NOTES (insn);
3117   rtx link = *pprev;
3118   rtx dead = NULL;
3119   rtx unused = NULL;
3120
3121   while (link)
3122     {
3123       switch (REG_NOTE_KIND (link))
3124         {
3125         case REG_DEAD:
3126           /* After reg-stack, we need to ignore any unused notes
3127              for the stack registers.  */
3128           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3129             {
3130               pprev = &XEXP (link, 1);
3131               link = *pprev;
3132             }
3133           else
3134             {
3135               rtx next = XEXP (link, 1);
3136 #ifdef REG_DEAD_DEBUGGING
3137               df_print_note ("deleting: ", insn, link);
3138 #endif
3139               XEXP (link, 1) = dead;
3140               dead = link;
3141               *pprev = link = next;
3142             }
3143           break;
3144
3145         case REG_UNUSED:
3146           /* After reg-stack, we need to ignore any unused notes
3147              for the stack registers.  */
3148           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3149             {
3150               pprev = &XEXP (link, 1);
3151               link = *pprev;
3152             }
3153           else
3154             {
3155               rtx next = XEXP (link, 1);
3156 #ifdef REG_DEAD_DEBUGGING
3157               df_print_note ("deleting: ", insn, link);
3158 #endif
3159               XEXP (link, 1) = unused;
3160               unused = link;
3161               *pprev = link = next;
3162             }
3163           break;
3164
3165         default:
3166           pprev = &XEXP (link, 1);
3167           link = *pprev;
3168           break;
3169         }
3170     }
3171
3172   *old_dead_notes = dead;
3173   *old_unused_notes = unused;
3174 }
3175
3176
3177 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
3178    list, otherwise create a new one.  */
3179
3180 static inline rtx
3181 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3182 {
3183   rtx curr = old;
3184   rtx prev = NULL;
3185
3186   gcc_assert (!DEBUG_INSN_P (insn));
3187
3188   while (curr)
3189     if (XEXP (curr, 0) == reg)
3190       {
3191         if (prev)
3192           XEXP (prev, 1) = XEXP (curr, 1);
3193         else
3194           old = XEXP (curr, 1);
3195         XEXP (curr, 1) = REG_NOTES (insn);
3196         REG_NOTES (insn) = curr;
3197         return old;
3198       }
3199     else
3200       {
3201         prev = curr;
3202         curr = XEXP (curr, 1);
3203       }
3204
3205   /* Did not find the note.  */
3206   add_reg_note (insn, note_type, reg);
3207   return old;
3208 }
3209
3210 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3211    arguments.  Return true if the register value described by MWS's
3212    mw_reg is known to be completely unused, and if mw_reg can therefore
3213    be used in a REG_UNUSED note.  */
3214
3215 static bool
3216 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3217                           bitmap live, bitmap artificial_uses)
3218 {
3219   unsigned int r;
3220
3221   /* If MWS describes a partial reference, create REG_UNUSED notes for
3222      individual hard registers.  */
3223   if (mws->flags & DF_REF_PARTIAL)
3224     return false;
3225
3226   /* Likewise if some part of the register is used.  */
3227   for (r = mws->start_regno; r <= mws->end_regno; r++)
3228     if (bitmap_bit_p (live, r)
3229         || bitmap_bit_p (artificial_uses, r))
3230       return false;
3231
3232   gcc_assert (REG_P (mws->mw_reg));
3233   return true;
3234 }
3235
3236 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3237    based on the bits in LIVE.  Do not generate notes for registers in
3238    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3239    not generated if the reg is both read and written by the
3240    instruction.
3241 */
3242
3243 static rtx
3244 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3245                             bitmap live, bitmap do_not_gen,
3246                             bitmap artificial_uses)
3247 {
3248   unsigned int r;
3249
3250 #ifdef REG_DEAD_DEBUGGING
3251   if (dump_file)
3252     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3253              mws->start_regno, mws->end_regno);
3254 #endif
3255
3256   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3257     {
3258       unsigned int regno = mws->start_regno;
3259       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3260
3261 #ifdef REG_DEAD_DEBUGGING
3262       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3263 #endif
3264       bitmap_set_bit (do_not_gen, regno);
3265       /* Only do this if the value is totally dead.  */
3266     }
3267   else
3268     for (r = mws->start_regno; r <= mws->end_regno; r++)
3269       {
3270         if (!bitmap_bit_p (live, r)
3271             && !bitmap_bit_p (artificial_uses, r))
3272           {
3273             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3274 #ifdef REG_DEAD_DEBUGGING
3275             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3276 #endif
3277           }
3278         bitmap_set_bit (do_not_gen, r);
3279       }
3280   return old;
3281 }
3282
3283
3284 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3285    arguments.  Return true if the register value described by MWS's
3286    mw_reg is known to be completely dead, and if mw_reg can therefore
3287    be used in a REG_DEAD note.  */
3288
3289 static bool
3290 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3291                         bitmap live, bitmap artificial_uses,
3292                         bitmap do_not_gen)
3293 {
3294   unsigned int r;
3295
3296   /* If MWS describes a partial reference, create REG_DEAD notes for
3297      individual hard registers.  */
3298   if (mws->flags & DF_REF_PARTIAL)
3299     return false;
3300
3301   /* Likewise if some part of the register is not dead.  */
3302   for (r = mws->start_regno; r <= mws->end_regno; r++)
3303     if (bitmap_bit_p (live, r)
3304         || bitmap_bit_p (artificial_uses, r)
3305         || bitmap_bit_p (do_not_gen, r))
3306       return false;
3307
3308   gcc_assert (REG_P (mws->mw_reg));
3309   return true;
3310 }
3311
3312 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3313    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3314    from being set if the instruction both reads and writes the
3315    register.  */
3316
3317 static rtx
3318 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3319                           bitmap live, bitmap do_not_gen,
3320                           bitmap artificial_uses, bool *added_notes_p)
3321 {
3322   unsigned int r;
3323   bool is_debug = *added_notes_p;
3324
3325   *added_notes_p = false;
3326
3327 #ifdef REG_DEAD_DEBUGGING
3328   if (dump_file)
3329     {
3330       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3331                mws->start_regno, mws->end_regno);
3332       df_print_regset (dump_file, do_not_gen);
3333       fprintf (dump_file, "  live =");
3334       df_print_regset (dump_file, live);
3335       fprintf (dump_file, "  artificial uses =");
3336       df_print_regset (dump_file, artificial_uses);
3337     }
3338 #endif
3339
3340   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3341     {
3342       /* Add a dead note for the entire multi word register.  */
3343       if (is_debug)
3344         {
3345           *added_notes_p = true;
3346           return old;
3347         }
3348       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3349 #ifdef REG_DEAD_DEBUGGING
3350       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3351 #endif
3352     }
3353   else
3354     {
3355       for (r = mws->start_regno; r <= mws->end_regno; r++)
3356         if (!bitmap_bit_p (live, r)
3357             && !bitmap_bit_p (artificial_uses, r)
3358             && !bitmap_bit_p (do_not_gen, r))
3359           {
3360             if (is_debug)
3361               {
3362                 *added_notes_p = true;
3363                 return old;
3364               }
3365             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3366 #ifdef REG_DEAD_DEBUGGING
3367             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3368 #endif
3369           }
3370     }
3371   return old;
3372 }
3373
3374
3375 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3376    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3377
3378 static rtx
3379 df_create_unused_note (rtx insn, rtx old, df_ref def,
3380                        bitmap live, bitmap artificial_uses)
3381 {
3382   unsigned int dregno = DF_REF_REGNO (def);
3383
3384 #ifdef REG_DEAD_DEBUGGING
3385   if (dump_file)
3386     {
3387       fprintf (dump_file, "  regular looking at def ");
3388       df_ref_debug (def, dump_file);
3389     }
3390 #endif
3391
3392   if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3393         || bitmap_bit_p (live, dregno)
3394         || bitmap_bit_p (artificial_uses, dregno)
3395         || df_ignore_stack_reg (dregno)))
3396     {
3397       rtx reg = (DF_REF_LOC (def))
3398                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3399       old = df_set_note (REG_UNUSED, insn, old, reg);
3400 #ifdef REG_DEAD_DEBUGGING
3401       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3402 #endif
3403     }
3404
3405   return old;
3406 }
3407
3408 /* Node of a linked list of uses of dead REGs in debug insns.  */
3409 struct dead_debug_use
3410 {
3411   df_ref use;
3412   struct dead_debug_use *next;
3413 };
3414
3415 /* Linked list of the above, with a bitmap of the REGs in the
3416    list.  */
3417 struct dead_debug
3418 {
3419   struct dead_debug_use *head;
3420   bitmap used;
3421   bitmap to_rescan;
3422 };
3423
3424 /* Initialize DEBUG to an empty list, and clear USED, if given.  */
3425 static inline void
3426 dead_debug_init (struct dead_debug *debug, bitmap used)
3427 {
3428   debug->head = NULL;
3429   debug->used = used;
3430   debug->to_rescan = NULL;
3431   if (used)
3432     bitmap_clear (used);
3433 }
3434
3435 /* Reset all debug insns with pending uses.  Release the bitmap in it,
3436    unless it is USED.  USED must be the same bitmap passed to
3437    dead_debug_init.  */
3438 static inline void
3439 dead_debug_finish (struct dead_debug *debug, bitmap used)
3440 {
3441   struct dead_debug_use *head;
3442   rtx insn = NULL;
3443
3444   if (debug->used != used)
3445     BITMAP_FREE (debug->used);
3446
3447   while ((head = debug->head))
3448     {
3449       insn = DF_REF_INSN (head->use);
3450       if (!head->next || DF_REF_INSN (head->next->use) != insn)
3451         {
3452           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3453           df_insn_rescan_debug_internal (insn);
3454           if (debug->to_rescan)
3455             bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));
3456         }
3457       debug->head = head->next;
3458       XDELETE (head);
3459     }
3460
3461   if (debug->to_rescan)
3462     {
3463       bitmap_iterator bi;
3464       unsigned int uid;
3465
3466       EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
3467         {
3468           struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
3469           if (insn_info)
3470             df_insn_rescan (insn_info->insn);
3471         }
3472       BITMAP_FREE (debug->to_rescan);
3473     }
3474 }
3475
3476 /* Add USE to DEBUG.  It must be a dead reference to UREGNO in a debug
3477    insn.  Create a bitmap for DEBUG as needed.  */
3478 static inline void
3479 dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
3480 {
3481   struct dead_debug_use *newddu = XNEW (struct dead_debug_use);
3482
3483   newddu->use = use;
3484   newddu->next = debug->head;
3485   debug->head = newddu;
3486
3487   if (!debug->used)
3488     debug->used = BITMAP_ALLOC (NULL);
3489
3490   bitmap_set_bit (debug->used, uregno);
3491 }
3492
3493 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3494    before INSN that binds the REG to a debug temp, and replace all
3495    uses of UREGNO in DEBUG with uses of the debug temp.  INSN must be
3496    the insn where UREGNO dies.  */
3497 static inline void
3498 dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
3499                           rtx insn)
3500 {
3501   struct dead_debug_use **tailp = &debug->head;
3502   struct dead_debug_use *cur;
3503   struct dead_debug_use *uses = NULL;
3504   struct dead_debug_use **usesp = &uses;
3505   rtx reg = NULL;
3506   rtx dval;
3507   rtx bind;
3508
3509   if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
3510     return;
3511
3512   /* Move all uses of uregno from debug->head to uses, setting mode to
3513      the widest referenced mode.  */
3514   while ((cur = *tailp))
3515     {
3516       if (DF_REF_REGNO (cur->use) == uregno)
3517         {
3518           *usesp = cur;
3519           usesp = &cur->next;
3520           *tailp = cur->next;
3521           cur->next = NULL;
3522           if (!reg
3523               || (GET_MODE_BITSIZE (GET_MODE (reg))
3524                   < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
3525             reg = *DF_REF_REAL_LOC (cur->use);
3526         }
3527       else
3528         tailp = &(*tailp)->next;
3529     }
3530
3531   gcc_assert (reg);
3532
3533   /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL).  */
3534   dval = make_debug_expr_from_rtl (reg);
3535
3536   /* Emit a debug bind insn before the insn in which reg dies.  */
3537   bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
3538                                DEBUG_EXPR_TREE_DECL (dval), reg,
3539                                VAR_INIT_STATUS_INITIALIZED);
3540
3541   bind = emit_debug_insn_before (bind, insn);
3542   df_insn_rescan (bind);
3543
3544   /* Adjust all uses.  */
3545   while ((cur = uses))
3546     {
3547       if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
3548         *DF_REF_REAL_LOC (cur->use) = dval;
3549       else
3550         *DF_REF_REAL_LOC (cur->use)
3551           = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
3552       /* ??? Should we simplify subreg of subreg?  */
3553       if (debug->to_rescan == NULL)
3554         debug->to_rescan = BITMAP_ALLOC (NULL);
3555       bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
3556       uses = cur->next;
3557       XDELETE (cur);
3558     }
3559 }
3560
3561 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3562    info: lifetime, bb, and number of defs and uses for basic block
3563    BB.  The three bitvectors are scratch regs used here.  */
3564
3565 static void
3566 df_note_bb_compute (unsigned int bb_index,
3567                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3568 {
3569   basic_block bb = BASIC_BLOCK (bb_index);
3570   rtx insn;
3571   df_ref *def_rec;
3572   df_ref *use_rec;
3573   struct dead_debug debug;
3574
3575   dead_debug_init (&debug, NULL);
3576
3577   bitmap_copy (live, df_get_live_out (bb));
3578   bitmap_clear (artificial_uses);
3579
3580 #ifdef REG_DEAD_DEBUGGING
3581   if (dump_file)
3582     {
3583       fprintf (dump_file, "live at bottom ");
3584       df_print_regset (dump_file, live);
3585     }
3586 #endif
3587
3588   /* Process the artificial defs and uses at the bottom of the block
3589      to begin processing.  */
3590   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3591     {
3592       df_ref def = *def_rec;
3593 #ifdef REG_DEAD_DEBUGGING
3594       if (dump_file)
3595         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3596 #endif
3597
3598       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3599         bitmap_clear_bit (live, DF_REF_REGNO (def));
3600     }
3601
3602   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3603     {
3604       df_ref use = *use_rec;
3605       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3606         {
3607           unsigned int regno = DF_REF_REGNO (use);
3608           bitmap_set_bit (live, regno);
3609
3610           /* Notes are not generated for any of the artificial registers
3611              at the bottom of the block.  */
3612           bitmap_set_bit (artificial_uses, regno);
3613         }
3614     }
3615
3616 #ifdef REG_DEAD_DEBUGGING
3617   if (dump_file)
3618     {
3619       fprintf (dump_file, "live before artificials out ");
3620       df_print_regset (dump_file, live);
3621     }
3622 #endif
3623
3624   FOR_BB_INSNS_REVERSE (bb, insn)
3625     {
3626       unsigned int uid = INSN_UID (insn);
3627       struct df_mw_hardreg **mws_rec;
3628       rtx old_dead_notes;
3629       rtx old_unused_notes;
3630       int debug_insn;
3631
3632       if (!INSN_P (insn))
3633         continue;
3634
3635       debug_insn = DEBUG_INSN_P (insn);
3636
3637       bitmap_clear (do_not_gen);
3638       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3639
3640       /* Process the defs.  */
3641       if (CALL_P (insn))
3642         {
3643 #ifdef REG_DEAD_DEBUGGING
3644           if (dump_file)
3645             {
3646               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3647               df_print_regset (dump_file, live);
3648             }
3649 #endif
3650           /* We only care about real sets for calls.  Clobbers cannot
3651              be depended on to really die.  */
3652           mws_rec = DF_INSN_UID_MWS (uid);
3653           while (*mws_rec)
3654             {
3655               struct df_mw_hardreg *mws = *mws_rec;
3656               if ((DF_MWS_REG_DEF_P (mws))
3657                   && !df_ignore_stack_reg (mws->start_regno))
3658                 old_unused_notes
3659                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3660                                                 mws, live, do_not_gen,
3661                                                 artificial_uses);
3662               mws_rec++;
3663             }
3664
3665           /* All of the defs except the return value are some sort of
3666              clobber.  This code is for the return.  */
3667           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3668             {
3669               df_ref def = *def_rec;
3670               unsigned int dregno = DF_REF_REGNO (def);
3671               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3672                 {
3673                   old_unused_notes
3674                     = df_create_unused_note (insn, old_unused_notes,
3675                                              def, live, artificial_uses);
3676                   bitmap_set_bit (do_not_gen, dregno);
3677                 }
3678
3679               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3680                 bitmap_clear_bit (live, dregno);
3681             }
3682         }
3683       else
3684         {
3685           /* Regular insn.  */
3686           mws_rec = DF_INSN_UID_MWS (uid);
3687           while (*mws_rec)
3688             {
3689               struct df_mw_hardreg *mws = *mws_rec;
3690               if (DF_MWS_REG_DEF_P (mws))
3691                 old_unused_notes
3692                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3693                                                 mws, live, do_not_gen,
3694                                                 artificial_uses);
3695               mws_rec++;
3696             }
3697
3698           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3699             {
3700               df_ref def = *def_rec;
3701               unsigned int dregno = DF_REF_REGNO (def);
3702               old_unused_notes
3703                 = df_create_unused_note (insn, old_unused_notes,
3704                                          def, live, artificial_uses);
3705
3706               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3707                 bitmap_set_bit (do_not_gen, dregno);
3708
3709               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3710                 bitmap_clear_bit (live, dregno);
3711             }
3712         }
3713
3714       /* Process the uses.  */
3715       mws_rec = DF_INSN_UID_MWS (uid);
3716       while (*mws_rec)
3717         {
3718           struct df_mw_hardreg *mws = *mws_rec;
3719           if ((DF_MWS_REG_DEF_P (mws))
3720               && !df_ignore_stack_reg (mws->start_regno))
3721             {
3722               bool really_add_notes = debug_insn != 0;
3723
3724               old_dead_notes
3725                 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3726                                             mws, live, do_not_gen,
3727                                             artificial_uses,
3728                                             &really_add_notes);
3729
3730               if (really_add_notes)
3731                 debug_insn = -1;
3732             }
3733           mws_rec++;
3734         }
3735
3736       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3737         {
3738           df_ref use = *use_rec;
3739           unsigned int uregno = DF_REF_REGNO (use);
3740
3741 #ifdef REG_DEAD_DEBUGGING
3742           if (dump_file && !debug_insn)
3743             {
3744               fprintf (dump_file, "  regular looking at use ");
3745               df_ref_debug (use, dump_file);
3746             }
3747 #endif
3748           if (!bitmap_bit_p (live, uregno))
3749             {
3750               if (debug_insn)
3751                 {
3752                   if (debug_insn > 0)
3753                     {
3754                       dead_debug_add (&debug, use, uregno);
3755                       continue;
3756                     }
3757                   break;
3758                 }
3759               else
3760                 dead_debug_insert_before (&debug, uregno, insn);
3761
3762               if ( (!(DF_REF_FLAGS (use)
3763                       & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3764                    && (!bitmap_bit_p (do_not_gen, uregno))
3765                    && (!bitmap_bit_p (artificial_uses, uregno))
3766                    && (!df_ignore_stack_reg (uregno)))
3767                 {
3768                   rtx reg = (DF_REF_LOC (use))
3769                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3770                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3771
3772 #ifdef REG_DEAD_DEBUGGING
3773                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3774 #endif
3775                 }
3776               /* This register is now live.  */
3777               bitmap_set_bit (live, uregno);
3778             }
3779         }
3780
3781       while (old_unused_notes)
3782         {
3783           rtx next = XEXP (old_unused_notes, 1);
3784           free_EXPR_LIST_node (old_unused_notes);
3785           old_unused_notes = next;
3786         }
3787       while (old_dead_notes)
3788         {
3789           rtx next = XEXP (old_dead_notes, 1);
3790           free_EXPR_LIST_node (old_dead_notes);
3791           old_dead_notes = next;
3792         }
3793
3794       if (debug_insn == -1)
3795         {
3796           /* ??? We could probably do better here, replacing dead
3797              registers with their definitions.  */
3798           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3799           df_insn_rescan_debug_internal (insn);
3800         }
3801     }
3802
3803   dead_debug_finish (&debug, NULL);
3804 }
3805
3806
3807 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3808 static void
3809 df_note_compute (bitmap all_blocks)
3810 {
3811   unsigned int bb_index;
3812   bitmap_iterator bi;
3813   bitmap_head live, do_not_gen, artificial_uses;
3814
3815   bitmap_initialize (&live, &df_bitmap_obstack);
3816   bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3817   bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3818
3819 #ifdef REG_DEAD_DEBUGGING
3820   if (dump_file)
3821     print_rtl_with_bb (dump_file, get_insns());
3822 #endif
3823
3824   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3825   {
3826     df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3827   }
3828
3829   bitmap_clear (&live);
3830   bitmap_clear (&do_not_gen);
3831   bitmap_clear (&artificial_uses);
3832 }
3833
3834
3835 /* Free all storage associated with the problem.  */
3836
3837 static void
3838 df_note_free (void)
3839 {
3840   free (df_note);
3841 }
3842
3843
3844 /* All of the information associated every instance of the problem.  */
3845
3846 static struct df_problem problem_NOTE =
3847 {
3848   DF_NOTE,                    /* Problem id.  */
3849   DF_NONE,                    /* Direction.  */
3850   df_note_alloc,              /* Allocate the problem specific data.  */
3851   NULL,                       /* Reset global information.  */
3852   NULL,                       /* Free basic block info.  */
3853   df_note_compute,            /* Local compute function.  */
3854   NULL,                       /* Init the solution specific data.  */
3855   NULL,                       /* Iterative solver.  */
3856   NULL,                       /* Confluence operator 0.  */
3857   NULL,                       /* Confluence operator n.  */
3858   NULL,                       /* Transfer function.  */
3859   NULL,                       /* Finalize function.  */
3860   df_note_free,               /* Free all of the problem information.  */
3861   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3862   NULL,                       /* Debugging.  */
3863   NULL,                       /* Debugging start block.  */
3864   NULL,                       /* Debugging end block.  */
3865   NULL,                       /* Incremental solution verify start.  */
3866   NULL,                       /* Incremental solution verify end.  */
3867   &problem_LR,                /* Dependent problem.  */
3868   TV_DF_NOTE,                 /* Timing variable.  */
3869   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3870 };
3871
3872
3873 /* Create a new DATAFLOW instance and add it to an existing instance
3874    of DF.  The returned structure is what is used to get at the
3875    solution.  */
3876
3877 void
3878 df_note_add_problem (void)
3879 {
3880   df_add_problem (&problem_NOTE);
3881 }
3882
3883
3884
3885 \f
3886 /*----------------------------------------------------------------------------
3887    Functions for simulating the effects of single insns.
3888
3889    You can either simulate in the forwards direction, starting from
3890    the top of a block or the backwards direction from the end of the
3891    block.  If you go backwards, defs are examined first to clear bits,
3892    then uses are examined to set bits.  If you go forwards, defs are
3893    examined first to set bits, then REG_DEAD and REG_UNUSED notes
3894    are examined to clear bits.  In either case, the result of examining
3895    a def can be undone (respectively by a use or a REG_UNUSED note).
3896
3897    If you start at the top of the block, use one of DF_LIVE_IN or
3898    DF_LR_IN.  If you start at the bottom of the block use one of
3899    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3900    THEY WILL BE DESTROYED.
3901 ----------------------------------------------------------------------------*/
3902
3903
3904 /* Find the set of DEFs for INSN.  */
3905
3906 void
3907 df_simulate_find_defs (rtx insn, bitmap defs)
3908 {
3909   df_ref *def_rec;
3910   unsigned int uid = INSN_UID (insn);
3911
3912   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3913     {
3914       df_ref def = *def_rec;
3915       bitmap_set_bit (defs, DF_REF_REGNO (def));
3916     }
3917 }
3918
3919 /* Find the set of real DEFs, which are not clobbers, for INSN.  */
3920
3921 void
3922 df_simulate_find_noclobber_defs (rtx insn, bitmap defs)
3923 {
3924   df_ref *def_rec;
3925   unsigned int uid = INSN_UID (insn);
3926
3927   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3928     {
3929       df_ref def = *def_rec;
3930       if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3931         bitmap_set_bit (defs, DF_REF_REGNO (def));
3932     }
3933 }
3934
3935
3936 /* Simulate the effects of the defs of INSN on LIVE.  */
3937
3938 void
3939 df_simulate_defs (rtx insn, bitmap live)
3940 {
3941   df_ref *def_rec;
3942   unsigned int uid = INSN_UID (insn);
3943
3944   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3945     {
3946       df_ref def = *def_rec;
3947       unsigned int dregno = DF_REF_REGNO (def);
3948
3949       /* If the def is to only part of the reg, it does
3950          not kill the other defs that reach here.  */
3951       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3952         bitmap_clear_bit (live, dregno);
3953     }
3954 }
3955
3956
3957 /* Simulate the effects of the uses of INSN on LIVE.  */
3958
3959 void
3960 df_simulate_uses (rtx insn, bitmap live)
3961 {
3962   df_ref *use_rec;
3963   unsigned int uid = INSN_UID (insn);
3964
3965   if (DEBUG_INSN_P (insn))
3966     return;
3967
3968   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3969     {
3970       df_ref use = *use_rec;
3971       /* Add use to set of uses in this BB.  */
3972       bitmap_set_bit (live, DF_REF_REGNO (use));
3973     }
3974 }
3975
3976
3977 /* Add back the always live regs in BB to LIVE.  */
3978
3979 static inline void
3980 df_simulate_fixup_sets (basic_block bb, bitmap live)
3981 {
3982   /* These regs are considered always live so if they end up dying
3983      because of some def, we need to bring the back again.  */
3984   if (bb_has_eh_pred (bb))
3985     bitmap_ior_into (live, &df->eh_block_artificial_uses);
3986   else
3987     bitmap_ior_into (live, &df->regular_block_artificial_uses);
3988 }
3989
3990
3991 /*----------------------------------------------------------------------------
3992    The following three functions are used only for BACKWARDS scanning:
3993    i.e. they process the defs before the uses.
3994
3995    df_simulate_initialize_backwards should be called first with a
3996    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3997    df_simulate_one_insn_backwards should be called for each insn in
3998    the block, starting with the last one.  Finally,
3999    df_simulate_finalize_backwards can be called to get a new value
4000    of the sets at the top of the block (this is rarely used).
4001    ----------------------------------------------------------------------------*/
4002
4003 /* Apply the artificial uses and defs at the end of BB in a backwards
4004    direction.  */
4005
4006 void
4007 df_simulate_initialize_backwards (basic_block bb, bitmap live)
4008 {
4009   df_ref *def_rec;
4010   df_ref *use_rec;
4011   int bb_index = bb->index;
4012
4013   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4014     {
4015       df_ref def = *def_rec;
4016       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
4017         bitmap_clear_bit (live, DF_REF_REGNO (def));
4018     }
4019
4020   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4021     {
4022       df_ref use = *use_rec;
4023       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
4024         bitmap_set_bit (live, DF_REF_REGNO (use));
4025     }
4026 }
4027
4028
4029 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
4030
4031 void
4032 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
4033 {
4034   if (!NONDEBUG_INSN_P (insn))
4035     return;
4036
4037   df_simulate_defs (insn, live);
4038   df_simulate_uses (insn, live);
4039   df_simulate_fixup_sets (bb, live);
4040 }
4041
4042
4043 /* Apply the artificial uses and defs at the top of BB in a backwards
4044    direction.  */
4045
4046 void
4047 df_simulate_finalize_backwards (basic_block bb, bitmap live)
4048 {
4049   df_ref *def_rec;
4050 #ifdef EH_USES
4051   df_ref *use_rec;
4052 #endif
4053   int bb_index = bb->index;
4054
4055   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4056     {
4057       df_ref def = *def_rec;
4058       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4059         bitmap_clear_bit (live, DF_REF_REGNO (def));
4060     }
4061
4062 #ifdef EH_USES
4063   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4064     {
4065       df_ref use = *use_rec;
4066       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4067         bitmap_set_bit (live, DF_REF_REGNO (use));
4068     }
4069 #endif
4070 }
4071 /*----------------------------------------------------------------------------
4072    The following three functions are used only for FORWARDS scanning:
4073    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
4074    Thus it is important to add the DF_NOTES problem to the stack of
4075    problems computed before using these functions.
4076
4077    df_simulate_initialize_forwards should be called first with a
4078    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
4079    df_simulate_one_insn_forwards should be called for each insn in
4080    the block, starting with the first one.
4081    ----------------------------------------------------------------------------*/
4082
4083 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
4084    DF_LR_IN for basic block BB, for forward scanning by marking artificial
4085    defs live.  */
4086
4087 void
4088 df_simulate_initialize_forwards (basic_block bb, bitmap live)
4089 {
4090   df_ref *def_rec;
4091   int bb_index = bb->index;
4092
4093   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4094     {
4095       df_ref def = *def_rec;
4096       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4097         bitmap_set_bit (live, DF_REF_REGNO (def));
4098     }
4099 }
4100
4101 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
4102
4103 void
4104 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4105 {
4106   rtx link;
4107   if (! INSN_P (insn))
4108     return;
4109
4110   /* Make sure that DF_NOTE really is an active df problem.  */
4111   gcc_assert (df_note);
4112
4113   /* Note that this is the opposite as how the problem is defined, because
4114      in the LR problem defs _kill_ liveness.  However, they do so backwards,
4115      while here the scan is performed forwards!  So, first assume that the
4116      def is live, and if this is not true REG_UNUSED notes will rectify the
4117      situation.  */
4118   df_simulate_find_noclobber_defs (insn, live);
4119
4120   /* Clear all of the registers that go dead.  */
4121   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4122     {
4123       switch (REG_NOTE_KIND (link))
4124         {
4125         case REG_DEAD:
4126         case REG_UNUSED:
4127           {
4128             rtx reg = XEXP (link, 0);
4129             int regno = REGNO (reg);
4130             if (regno < FIRST_PSEUDO_REGISTER)
4131               {
4132                 int n = hard_regno_nregs[regno][GET_MODE (reg)];
4133                 while (--n >= 0)
4134                   bitmap_clear_bit (live, regno + n);
4135               }
4136             else
4137               bitmap_clear_bit (live, regno);
4138           }
4139           break;
4140         default:
4141           break;
4142         }
4143     }
4144   df_simulate_fixup_sets (bb, live);
4145 }
4146
4147
4148 \f
4149 /*----------------------------------------------------------------------------
4150    MULTIPLE DEFINITIONS
4151
4152    Find the locations in the function reached by multiple definition sites
4153    for a live pseudo.  In and out bitvectors are built for each basic
4154    block.  They are restricted for efficiency to live registers.
4155
4156    The gen and kill sets for the problem are obvious.  Together they
4157    include all defined registers in a basic block; the gen set includes
4158    registers where a partial or conditional or may-clobber definition is
4159    last in the BB, while the kill set includes registers with a complete
4160    definition coming last.  However, the computation of the dataflow
4161    itself is interesting.
4162
4163    The idea behind it comes from SSA form's iterated dominance frontier
4164    criterion for inserting PHI functions.  Just like in that case, we can use
4165    the dominance frontier to find places where multiple definitions meet;
4166    a register X defined in a basic block BB1 has multiple definitions in
4167    basic blocks in BB1's dominance frontier.
4168
4169    So, the in-set of a basic block BB2 is not just the union of the
4170    out-sets of BB2's predecessors, but includes some more bits that come
4171    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4172    the previous paragraph).  I called this set the init-set of BB2.
4173
4174       (Note: I actually use the kill-set only to build the init-set.
4175       gen bits are anyway propagated from BB1 to BB2 by dataflow).
4176
4177     For example, if you have
4178
4179        BB1 : r10 = 0
4180              r11 = 0
4181              if <...> goto BB2 else goto BB3;
4182
4183        BB2 : r10 = 1
4184              r12 = 1
4185              goto BB3;
4186
4187        BB3 :
4188
4189     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4190     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
4191     not need to iterate the dominance frontier, because we do not insert
4192     anything like PHI functions there!  Instead, dataflow will take care of
4193     propagating the information to BB3's successors.
4194    ---------------------------------------------------------------------------*/
4195
4196 /* Scratch var used by transfer functions.  This is used to do md analysis
4197    only for live registers.  */
4198 static bitmap_head df_md_scratch;
4199
4200 /* Set basic block info.  */
4201
4202 static void
4203 df_md_set_bb_info (unsigned int index,
4204                    struct df_md_bb_info *bb_info)
4205 {
4206   gcc_assert (df_md);
4207   gcc_assert (index < df_md->block_info_size);
4208   df_md->block_info[index] = bb_info;
4209 }
4210
4211
4212 static void
4213 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4214                     void *vbb_info)
4215 {
4216   struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4217   if (bb_info)
4218     {
4219       bitmap_clear (&bb_info->kill);
4220       bitmap_clear (&bb_info->gen);
4221       bitmap_clear (&bb_info->init);
4222       bitmap_clear (&bb_info->in);
4223       bitmap_clear (&bb_info->out);
4224       pool_free (df_md->block_pool, bb_info);
4225     }
4226 }
4227
4228
4229 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4230    not touched unless the block is new.  */
4231
4232 static void
4233 df_md_alloc (bitmap all_blocks)
4234 {
4235   unsigned int bb_index;
4236   bitmap_iterator bi;
4237
4238   if (!df_md->block_pool)
4239     df_md->block_pool = create_alloc_pool ("df_md_block pool",
4240                                            sizeof (struct df_md_bb_info), 50);
4241
4242   df_grow_bb_info (df_md);
4243   bitmap_initialize (&df_md_scratch, &bitmap_default_obstack);
4244
4245   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4246     {
4247       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4248       if (bb_info)
4249         {
4250           bitmap_clear (&bb_info->init);
4251           bitmap_clear (&bb_info->gen);
4252           bitmap_clear (&bb_info->kill);
4253           bitmap_clear (&bb_info->in);
4254           bitmap_clear (&bb_info->out);
4255         }
4256       else
4257         {
4258           bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
4259           df_md_set_bb_info (bb_index, bb_info);
4260           bitmap_initialize (&bb_info->init, &bitmap_default_obstack);
4261           bitmap_initialize (&bb_info->gen, &bitmap_default_obstack);
4262           bitmap_initialize (&bb_info->kill, &bitmap_default_obstack);
4263           bitmap_initialize (&bb_info->in, &bitmap_default_obstack);
4264           bitmap_initialize (&bb_info->out, &bitmap_default_obstack);
4265         }
4266     }
4267
4268   df_md->optional_p = true;
4269 }
4270
4271 /* Add the effect of the top artificial defs of BB to the multiple definitions
4272    bitmap LOCAL_MD.  */
4273
4274 void
4275 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4276 {
4277   int bb_index = bb->index;
4278   df_ref *def_rec;
4279   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4280     {
4281       df_ref def = *def_rec;
4282       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4283         {
4284           unsigned int dregno = DF_REF_REGNO (def);
4285           if (DF_REF_FLAGS (def)
4286               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4287             bitmap_set_bit (local_md, dregno);
4288           else
4289             bitmap_clear_bit (local_md, dregno);
4290         }
4291     }
4292 }
4293
4294
4295 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4296    LOCAL_MD.  */
4297
4298 void
4299 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4300                         bitmap local_md)
4301 {
4302   unsigned uid = INSN_UID (insn);
4303   df_ref *def_rec;
4304
4305   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4306     {
4307       df_ref def = *def_rec;
4308       unsigned int dregno = DF_REF_REGNO (def);
4309       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4310           || (dregno >= FIRST_PSEUDO_REGISTER))
4311         {
4312           if (DF_REF_FLAGS (def)
4313               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4314            bitmap_set_bit (local_md, DF_REF_ID (def));
4315          else
4316            bitmap_clear_bit (local_md, DF_REF_ID (def));
4317         }
4318     }
4319 }
4320
4321 static void
4322 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4323                                     df_ref *def_rec,
4324                                     int top_flag)
4325 {
4326   df_ref def;
4327   bitmap_clear (&seen_in_insn);
4328
4329   while ((def = *def_rec++) != NULL)
4330     {
4331       unsigned int dregno = DF_REF_REGNO (def);
4332       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4333             || (dregno >= FIRST_PSEUDO_REGISTER))
4334           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4335         {
4336           if (!bitmap_bit_p (&seen_in_insn, dregno))
4337             {
4338               if (DF_REF_FLAGS (def)
4339                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4340                 {
4341                   bitmap_set_bit (&bb_info->gen, dregno);
4342                   bitmap_clear_bit (&bb_info->kill, dregno);
4343                 }
4344               else
4345                 {
4346                   /* When we find a clobber and a regular def,
4347                      make sure the regular def wins.  */
4348                   bitmap_set_bit (&seen_in_insn, dregno);
4349                   bitmap_set_bit (&bb_info->kill, dregno);
4350                   bitmap_clear_bit (&bb_info->gen, dregno);
4351                 }
4352             }
4353         }
4354     }
4355 }
4356
4357
4358 /* Compute local multiple def info for basic block BB.  */
4359
4360 static void
4361 df_md_bb_local_compute (unsigned int bb_index)
4362 {
4363   basic_block bb = BASIC_BLOCK (bb_index);
4364   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4365   rtx insn;
4366
4367   /* Artificials are only hard regs.  */
4368   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4369     df_md_bb_local_compute_process_def (bb_info,
4370                                         df_get_artificial_defs (bb_index),
4371                                         DF_REF_AT_TOP);
4372
4373   FOR_BB_INSNS (bb, insn)
4374     {
4375       unsigned int uid = INSN_UID (insn);
4376       if (!INSN_P (insn))
4377         continue;
4378
4379       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4380     }
4381
4382   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4383     df_md_bb_local_compute_process_def (bb_info,
4384                                         df_get_artificial_defs (bb_index),
4385                                         0);
4386 }
4387
4388 /* Compute local reaching def info for each basic block within BLOCKS.  */
4389
4390 static void
4391 df_md_local_compute (bitmap all_blocks)
4392 {
4393   unsigned int bb_index, df_bb_index;
4394   bitmap_iterator bi1, bi2;
4395   basic_block bb;
4396   bitmap_head *frontiers;
4397
4398   bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4399
4400   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4401     {
4402       df_md_bb_local_compute (bb_index);
4403     }
4404
4405   bitmap_clear (&seen_in_insn);
4406
4407   frontiers = XNEWVEC (bitmap_head, last_basic_block);
4408   FOR_ALL_BB (bb)
4409     bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4410
4411   compute_dominance_frontiers (frontiers);
4412
4413   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
4414   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4415     {
4416       bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4417       EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4418         {
4419           basic_block bb = BASIC_BLOCK (df_bb_index);
4420           if (bitmap_bit_p (all_blocks, df_bb_index))
4421             bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4422                                  df_get_live_in (bb));
4423         }
4424     }
4425
4426   FOR_ALL_BB (bb)
4427     bitmap_clear (&frontiers[bb->index]);
4428   free (frontiers);
4429 }
4430
4431
4432 /* Reset the global solution for recalculation.  */
4433
4434 static void
4435 df_md_reset (bitmap all_blocks)
4436 {
4437   unsigned int bb_index;
4438   bitmap_iterator bi;
4439
4440   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4441     {
4442       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4443       gcc_assert (bb_info);
4444       bitmap_clear (&bb_info->in);
4445       bitmap_clear (&bb_info->out);
4446     }
4447 }
4448
4449 static bool
4450 df_md_transfer_function (int bb_index)
4451 {
4452   basic_block bb = BASIC_BLOCK (bb_index);
4453   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4454   bitmap in = &bb_info->in;
4455   bitmap out = &bb_info->out;
4456   bitmap gen = &bb_info->gen;
4457   bitmap kill = &bb_info->kill;
4458
4459   /* We need to use a scratch set here so that the value returned from this
4460      function invocation properly reflects whether the sets changed in a
4461      significant way; i.e. not just because the live set was anded in.  */
4462   bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4463
4464   /* Multiple definitions of a register are not relevant if it is not
4465      live.  Thus we trim the result to the places where it is live.  */
4466   bitmap_and_into (in, df_get_live_in (bb));
4467
4468   return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4469 }
4470
4471 /* Initialize the solution bit vectors for problem.  */
4472
4473 static void
4474 df_md_init (bitmap all_blocks)
4475 {
4476   unsigned int bb_index;
4477   bitmap_iterator bi;
4478
4479   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4480     {
4481       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4482
4483       bitmap_copy (&bb_info->in, &bb_info->init);
4484       df_md_transfer_function (bb_index);
4485     }
4486 }
4487
4488 static void
4489 df_md_confluence_0 (basic_block bb)
4490 {
4491   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4492   bitmap_copy (&bb_info->in, &bb_info->init);
4493 }
4494
4495 /* In of target gets or of out of source.  */
4496
4497 static void
4498 df_md_confluence_n (edge e)
4499 {
4500   bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4501   bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4502
4503   if (e->flags & EDGE_FAKE)
4504     return;
4505
4506   if (e->flags & EDGE_EH)
4507     bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
4508   else
4509     bitmap_ior_into (op1, op2);
4510 }
4511
4512 /* Free all storage associated with the problem.  */
4513
4514 static void
4515 df_md_free (void)
4516 {
4517   unsigned int i;
4518   for (i = 0; i < df_md->block_info_size; i++)
4519     {
4520       struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
4521       if (bb_info)
4522         {
4523           bitmap_clear (&bb_info->kill);
4524           bitmap_clear (&bb_info->gen);
4525           bitmap_clear (&bb_info->init);
4526           bitmap_clear (&bb_info->in);
4527           bitmap_clear (&bb_info->out);
4528         }
4529     }
4530
4531   bitmap_clear (&df_md_scratch);
4532   free_alloc_pool (df_md->block_pool);
4533
4534   df_md->block_info_size = 0;
4535   free (df_md->block_info);
4536   free (df_md);
4537 }
4538
4539
4540 /* Debugging info at top of bb.  */
4541
4542 static void
4543 df_md_top_dump (basic_block bb, FILE *file)
4544 {
4545   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4546   if (!bb_info)
4547     return;
4548
4549   fprintf (file, ";; md  in  \t");
4550   df_print_regset (file, &bb_info->in);
4551   fprintf (file, ";; md  init  \t");
4552   df_print_regset (file, &bb_info->init);
4553   fprintf (file, ";; md  gen \t");
4554   df_print_regset (file, &bb_info->gen);
4555   fprintf (file, ";; md  kill \t");
4556   df_print_regset (file, &bb_info->kill);
4557 }
4558
4559 /* Debugging info at bottom of bb.  */
4560
4561 static void
4562 df_md_bottom_dump (basic_block bb, FILE *file)
4563 {
4564   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4565   if (!bb_info)
4566     return;
4567
4568   fprintf (file, ";; md  out \t");
4569   df_print_regset (file, &bb_info->out);
4570 }
4571
4572 static struct df_problem problem_MD =
4573 {
4574   DF_MD,                      /* Problem id.  */
4575   DF_FORWARD,                 /* Direction.  */
4576   df_md_alloc,                /* Allocate the problem specific data.  */
4577   df_md_reset,                /* Reset global information.  */
4578   df_md_free_bb_info,         /* Free basic block info.  */
4579   df_md_local_compute,        /* Local compute function.  */
4580   df_md_init,                 /* Init the solution specific data.  */
4581   df_worklist_dataflow,       /* Worklist solver.  */
4582   df_md_confluence_0,         /* Confluence operator 0.  */
4583   df_md_confluence_n,         /* Confluence operator n.  */
4584   df_md_transfer_function,    /* Transfer function.  */
4585   NULL,                       /* Finalize function.  */
4586   df_md_free,                 /* Free all of the problem information.  */
4587   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4588   NULL,                       /* Debugging.  */
4589   df_md_top_dump,             /* Debugging start block.  */
4590   df_md_bottom_dump,          /* Debugging end block.  */
4591   NULL,                       /* Incremental solution verify start.  */
4592   NULL,                       /* Incremental solution verify end.  */
4593   NULL,                       /* Dependent problem.  */
4594   TV_DF_MD,                   /* Timing variable.  */
4595   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4596 };
4597
4598 /* Create a new MD instance and add it to the existing instance
4599    of DF.  */
4600
4601 void
4602 df_md_add_problem (void)
4603 {
4604   df_add_problem (&problem_MD);
4605 }
4606
4607
4608