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