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