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 (!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   while (curr)
3186     if (XEXP (curr, 0) == reg)
3187       {
3188         if (prev)
3189           XEXP (prev, 1) = XEXP (curr, 1);
3190         else
3191           old = XEXP (curr, 1);
3192         XEXP (curr, 1) = REG_NOTES (insn);
3193         REG_NOTES (insn) = curr;
3194         return old;
3195       }
3196     else
3197       {
3198         prev = curr;
3199         curr = XEXP (curr, 1);
3200       }
3201
3202   /* Did not find the note.  */
3203   add_reg_note (insn, note_type, reg);
3204   return old;
3205 }
3206
3207 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3208    arguments.  Return true if the register value described by MWS's
3209    mw_reg is known to be completely unused, and if mw_reg can therefore
3210    be used in a REG_UNUSED note.  */
3211
3212 static bool
3213 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3214                           bitmap live, bitmap artificial_uses)
3215 {
3216   unsigned int r;
3217
3218   /* If MWS describes a partial reference, create REG_UNUSED notes for
3219      individual hard registers.  */
3220   if (mws->flags & DF_REF_PARTIAL)
3221     return false;
3222
3223   /* Likewise if some part of the register is used.  */
3224   for (r = mws->start_regno; r <= mws->end_regno; r++)
3225     if (bitmap_bit_p (live, r)
3226         || bitmap_bit_p (artificial_uses, r))
3227       return false;
3228
3229   gcc_assert (REG_P (mws->mw_reg));
3230   return true;
3231 }
3232
3233 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3234    based on the bits in LIVE.  Do not generate notes for registers in
3235    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3236    not generated if the reg is both read and written by the
3237    instruction.
3238 */
3239
3240 static rtx
3241 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3242                             bitmap live, bitmap do_not_gen,
3243                             bitmap artificial_uses)
3244 {
3245   unsigned int r;
3246
3247 #ifdef REG_DEAD_DEBUGGING
3248   if (dump_file)
3249     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3250              mws->start_regno, mws->end_regno);
3251 #endif
3252
3253   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3254     {
3255       unsigned int regno = mws->start_regno;
3256       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3257
3258 #ifdef REG_DEAD_DEBUGGING
3259       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3260 #endif
3261       bitmap_set_bit (do_not_gen, regno);
3262       /* Only do this if the value is totally dead.  */
3263     }
3264   else
3265     for (r = mws->start_regno; r <= mws->end_regno; r++)
3266       {
3267         if (!bitmap_bit_p (live, r)
3268             && !bitmap_bit_p (artificial_uses, r))
3269           {
3270             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3271 #ifdef REG_DEAD_DEBUGGING
3272             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3273 #endif
3274           }
3275         bitmap_set_bit (do_not_gen, r);
3276       }
3277   return old;
3278 }
3279
3280
3281 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3282    arguments.  Return true if the register value described by MWS's
3283    mw_reg is known to be completely dead, and if mw_reg can therefore
3284    be used in a REG_DEAD note.  */
3285
3286 static bool
3287 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3288                         bitmap live, bitmap artificial_uses,
3289                         bitmap do_not_gen)
3290 {
3291   unsigned int r;
3292
3293   /* If MWS describes a partial reference, create REG_DEAD notes for
3294      individual hard registers.  */
3295   if (mws->flags & DF_REF_PARTIAL)
3296     return false;
3297
3298   /* Likewise if some part of the register is not dead.  */
3299   for (r = mws->start_regno; r <= mws->end_regno; r++)
3300     if (bitmap_bit_p (live, r)
3301         || bitmap_bit_p (artificial_uses, r)
3302         || bitmap_bit_p (do_not_gen, r))
3303       return false;
3304
3305   gcc_assert (REG_P (mws->mw_reg));
3306   return true;
3307 }
3308
3309 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3310    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3311    from being set if the instruction both reads and writes the
3312    register.  */
3313
3314 static rtx
3315 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3316                           bitmap live, bitmap do_not_gen,
3317                           bitmap artificial_uses)
3318 {
3319   unsigned int r;
3320
3321 #ifdef REG_DEAD_DEBUGGING
3322   if (dump_file)
3323     {
3324       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3325                mws->start_regno, mws->end_regno);
3326       df_print_regset (dump_file, do_not_gen);
3327       fprintf (dump_file, "  live =");
3328       df_print_regset (dump_file, live);
3329       fprintf (dump_file, "  artificial uses =");
3330       df_print_regset (dump_file, artificial_uses);
3331     }
3332 #endif
3333
3334   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3335     {
3336       /* Add a dead note for the entire multi word register.  */
3337       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3338 #ifdef REG_DEAD_DEBUGGING
3339       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3340 #endif
3341     }
3342   else
3343     {
3344       for (r = mws->start_regno; r <= mws->end_regno; r++)
3345         if (!bitmap_bit_p (live, r)
3346             && !bitmap_bit_p (artificial_uses, r)
3347             && !bitmap_bit_p (do_not_gen, r))
3348           {
3349             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3350 #ifdef REG_DEAD_DEBUGGING
3351             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3352 #endif
3353           }
3354     }
3355   return old;
3356 }
3357
3358
3359 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3360    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3361
3362 static rtx
3363 df_create_unused_note (rtx insn, rtx old, df_ref def,
3364                        bitmap live, bitmap artificial_uses)
3365 {
3366   unsigned int dregno = DF_REF_REGNO (def);
3367
3368 #ifdef REG_DEAD_DEBUGGING
3369   if (dump_file)
3370     {
3371       fprintf (dump_file, "  regular looking at def ");
3372       df_ref_debug (def, dump_file);
3373     }
3374 #endif
3375
3376   if (!(bitmap_bit_p (live, dregno)
3377         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3378         || bitmap_bit_p (artificial_uses, dregno)
3379         || df_ignore_stack_reg (dregno)))
3380     {
3381       rtx reg = (DF_REF_LOC (def))
3382                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3383       old = df_set_note (REG_UNUSED, insn, old, reg);
3384 #ifdef REG_DEAD_DEBUGGING
3385       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3386 #endif
3387     }
3388
3389   return old;
3390 }
3391
3392
3393 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3394    info: lifetime, bb, and number of defs and uses for basic block
3395    BB.  The three bitvectors are scratch regs used here.  */
3396
3397 static void
3398 df_note_bb_compute (unsigned int bb_index,
3399                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3400 {
3401   basic_block bb = BASIC_BLOCK (bb_index);
3402   rtx insn;
3403   df_ref *def_rec;
3404   df_ref *use_rec;
3405
3406   bitmap_copy (live, df_get_live_out (bb));
3407   bitmap_clear (artificial_uses);
3408
3409 #ifdef REG_DEAD_DEBUGGING
3410   if (dump_file)
3411     {
3412       fprintf (dump_file, "live at bottom ");
3413       df_print_regset (dump_file, live);
3414     }
3415 #endif
3416
3417   /* Process the artificial defs and uses at the bottom of the block
3418      to begin processing.  */
3419   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3420     {
3421       df_ref def = *def_rec;
3422 #ifdef REG_DEAD_DEBUGGING
3423       if (dump_file)
3424         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3425 #endif
3426
3427       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3428         bitmap_clear_bit (live, DF_REF_REGNO (def));
3429     }
3430
3431   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3432     {
3433       df_ref use = *use_rec;
3434       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3435         {
3436           unsigned int regno = DF_REF_REGNO (use);
3437           bitmap_set_bit (live, regno);
3438
3439           /* Notes are not generated for any of the artificial registers
3440              at the bottom of the block.  */
3441           bitmap_set_bit (artificial_uses, regno);
3442         }
3443     }
3444
3445 #ifdef REG_DEAD_DEBUGGING
3446   if (dump_file)
3447     {
3448       fprintf (dump_file, "live before artificials out ");
3449       df_print_regset (dump_file, live);
3450     }
3451 #endif
3452
3453   FOR_BB_INSNS_REVERSE (bb, insn)
3454     {
3455       unsigned int uid = INSN_UID (insn);
3456       struct df_mw_hardreg **mws_rec;
3457       rtx old_dead_notes;
3458       rtx old_unused_notes;
3459
3460       if (!INSN_P (insn))
3461         continue;
3462
3463       bitmap_clear (do_not_gen);
3464       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3465
3466       /* Process the defs.  */
3467       if (CALL_P (insn))
3468         {
3469 #ifdef REG_DEAD_DEBUGGING
3470           if (dump_file)
3471             {
3472               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3473               df_print_regset (dump_file, live);
3474             }
3475 #endif
3476           /* We only care about real sets for calls.  Clobbers cannot
3477              be depended on to really die.  */
3478           mws_rec = DF_INSN_UID_MWS (uid);
3479           while (*mws_rec)
3480             {
3481               struct df_mw_hardreg *mws = *mws_rec;
3482               if ((DF_MWS_REG_DEF_P (mws))
3483                   && !df_ignore_stack_reg (mws->start_regno))
3484                 old_unused_notes
3485                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3486                                                 mws, live, do_not_gen,
3487                                                 artificial_uses);
3488               mws_rec++;
3489             }
3490
3491           /* All of the defs except the return value are some sort of
3492              clobber.  This code is for the return.  */
3493           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3494             {
3495               df_ref def = *def_rec;
3496               unsigned int dregno = DF_REF_REGNO (def);
3497               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3498                 {
3499                   old_unused_notes
3500                     = df_create_unused_note (insn, old_unused_notes,
3501                                              def, live, artificial_uses);
3502                   bitmap_set_bit (do_not_gen, dregno);
3503                 }
3504
3505               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3506                 bitmap_clear_bit (live, dregno);
3507             }
3508         }
3509       else
3510         {
3511           /* Regular insn.  */
3512           mws_rec = DF_INSN_UID_MWS (uid);
3513           while (*mws_rec)
3514             {
3515               struct df_mw_hardreg *mws = *mws_rec;
3516               if (DF_MWS_REG_DEF_P (mws))
3517                 old_unused_notes
3518                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3519                                                 mws, live, do_not_gen,
3520                                                 artificial_uses);
3521               mws_rec++;
3522             }
3523
3524           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3525             {
3526               df_ref def = *def_rec;
3527               unsigned int dregno = DF_REF_REGNO (def);
3528               old_unused_notes
3529                 = df_create_unused_note (insn, old_unused_notes,
3530                                          def, live, artificial_uses);
3531
3532               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3533                 bitmap_set_bit (do_not_gen, dregno);
3534
3535               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3536                 bitmap_clear_bit (live, dregno);
3537             }
3538         }
3539
3540       /* Process the uses.  */
3541       mws_rec = DF_INSN_UID_MWS (uid);
3542       while (*mws_rec)
3543         {
3544           struct df_mw_hardreg *mws = *mws_rec;
3545           if ((DF_MWS_REG_DEF_P (mws))
3546               && !df_ignore_stack_reg (mws->start_regno))
3547             old_dead_notes
3548               = df_set_dead_notes_for_mw (insn, old_dead_notes,
3549                                           mws, live, do_not_gen,
3550                                           artificial_uses);
3551           mws_rec++;
3552         }
3553
3554       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3555         {
3556           df_ref use = *use_rec;
3557           unsigned int uregno = DF_REF_REGNO (use);
3558
3559 #ifdef REG_DEAD_DEBUGGING
3560           if (dump_file)
3561             {
3562               fprintf (dump_file, "  regular looking at use ");
3563               df_ref_debug (use, dump_file);
3564             }
3565 #endif
3566           if (!bitmap_bit_p (live, uregno))
3567             {
3568               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3569                    && (!bitmap_bit_p (do_not_gen, uregno))
3570                    && (!bitmap_bit_p (artificial_uses, uregno))
3571                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3572                    && (!df_ignore_stack_reg (uregno)))
3573                 {
3574                   rtx reg = (DF_REF_LOC (use))
3575                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3576                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3577
3578 #ifdef REG_DEAD_DEBUGGING
3579                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3580 #endif
3581                 }
3582               /* This register is now live.  */
3583               bitmap_set_bit (live, uregno);
3584             }
3585         }
3586
3587       while (old_unused_notes)
3588         {
3589           rtx next = XEXP (old_unused_notes, 1);
3590           free_EXPR_LIST_node (old_unused_notes);
3591           old_unused_notes = next;
3592         }
3593       while (old_dead_notes)
3594         {
3595           rtx next = XEXP (old_dead_notes, 1);
3596           free_EXPR_LIST_node (old_dead_notes);
3597           old_dead_notes = next;
3598         }
3599     }
3600 }
3601
3602
3603 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3604 static void
3605 df_note_compute (bitmap all_blocks)
3606 {
3607   unsigned int bb_index;
3608   bitmap_iterator bi;
3609   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3610   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3611   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3612
3613 #ifdef REG_DEAD_DEBUGGING
3614   if (dump_file)
3615     print_rtl_with_bb (dump_file, get_insns());
3616 #endif
3617
3618   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3619   {
3620     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3621   }
3622
3623   BITMAP_FREE (live);
3624   BITMAP_FREE (do_not_gen);
3625   BITMAP_FREE (artificial_uses);
3626 }
3627
3628
3629 /* Free all storage associated with the problem.  */
3630
3631 static void
3632 df_note_free (void)
3633 {
3634   free (df_note);
3635 }
3636
3637
3638 /* All of the information associated every instance of the problem.  */
3639
3640 static struct df_problem problem_NOTE =
3641 {
3642   DF_NOTE,                    /* Problem id.  */
3643   DF_NONE,                    /* Direction.  */
3644   df_note_alloc,              /* Allocate the problem specific data.  */
3645   NULL,                       /* Reset global information.  */
3646   NULL,                       /* Free basic block info.  */
3647   df_note_compute,            /* Local compute function.  */
3648   NULL,                       /* Init the solution specific data.  */
3649   NULL,                       /* Iterative solver.  */
3650   NULL,                       /* Confluence operator 0.  */
3651   NULL,                       /* Confluence operator n.  */
3652   NULL,                       /* Transfer function.  */
3653   NULL,                       /* Finalize function.  */
3654   df_note_free,               /* Free all of the problem information.  */
3655   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3656   NULL,                       /* Debugging.  */
3657   NULL,                       /* Debugging start block.  */
3658   NULL,                       /* Debugging end block.  */
3659   NULL,                       /* Incremental solution verify start.  */
3660   NULL,                       /* Incremental solution verify end.  */
3661   &problem_LR,                /* Dependent problem.  */
3662   TV_DF_NOTE,                 /* Timing variable.  */
3663   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3664 };
3665
3666
3667 /* Create a new DATAFLOW instance and add it to an existing instance
3668    of DF.  The returned structure is what is used to get at the
3669    solution.  */
3670
3671 void
3672 df_note_add_problem (void)
3673 {
3674   df_add_problem (&problem_NOTE);
3675 }
3676
3677
3678
3679 \f
3680 /*----------------------------------------------------------------------------
3681    Functions for simulating the effects of single insns.
3682
3683    You can either simulate in the forwards direction, starting from
3684    the top of a block or the backwards direction from the end of the
3685    block.  The main difference is that if you go forwards, the uses
3686    are examined first then the defs, and if you go backwards, the defs
3687    are examined first then the uses.
3688
3689    If you start at the top of the block, use one of DF_LIVE_IN or
3690    DF_LR_IN.  If you start at the bottom of the block use one of
3691    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3692    THEY WILL BE DESTROYED.
3693 ----------------------------------------------------------------------------*/
3694
3695
3696 /* Find the set of DEFs for INSN.  */
3697
3698 void
3699 df_simulate_find_defs (rtx insn, bitmap defs)
3700 {
3701   df_ref *def_rec;
3702   unsigned int uid = INSN_UID (insn);
3703
3704   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3705     {
3706       df_ref def = *def_rec;
3707       /* If the def is to only part of the reg, it does
3708          not kill the other defs that reach here.  */
3709       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3710         bitmap_set_bit (defs, DF_REF_REGNO (def));
3711     }
3712 }
3713
3714
3715 /* Simulate the effects of the defs of INSN on LIVE.  */
3716
3717 void
3718 df_simulate_defs (rtx insn, bitmap live)
3719 {
3720   df_ref *def_rec;
3721   unsigned int uid = INSN_UID (insn);
3722
3723   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3724     {
3725       df_ref def = *def_rec;
3726       unsigned int dregno = DF_REF_REGNO (def);
3727
3728       /* If the def is to only part of the reg, it does
3729          not kill the other defs that reach here.  */
3730       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3731         bitmap_clear_bit (live, dregno);
3732     }
3733 }
3734
3735
3736 /* Simulate the effects of the uses of INSN on LIVE.  */
3737
3738 void
3739 df_simulate_uses (rtx insn, bitmap live)
3740 {
3741   df_ref *use_rec;
3742   unsigned int uid = INSN_UID (insn);
3743
3744   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3745     {
3746       df_ref use = *use_rec;
3747       /* Add use to set of uses in this BB.  */
3748       bitmap_set_bit (live, DF_REF_REGNO (use));
3749     }
3750 }
3751
3752
3753 /* Add back the always live regs in BB to LIVE.  */
3754
3755 static inline void
3756 df_simulate_fixup_sets (basic_block bb, bitmap live)
3757 {
3758   /* These regs are considered always live so if they end up dying
3759      because of some def, we need to bring the back again.  */
3760   if (bb_has_eh_pred (bb))
3761     bitmap_ior_into (live, df->eh_block_artificial_uses);
3762   else
3763     bitmap_ior_into (live, df->regular_block_artificial_uses);
3764 }
3765
3766
3767 /*----------------------------------------------------------------------------
3768    The following three functions are used only for BACKWARDS scanning:
3769    i.e. they process the defs before the uses.
3770
3771    df_simulate_initialize_backwards should be called first with a
3772    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3773    df_simulate_one_insn_backwards should be called for each insn in
3774    the block, starting with the last on.  Finally,
3775    df_simulate_finalize_backwards can be called to get a new value
3776    of the sets at the top of the block (this is rarely used).
3777    ----------------------------------------------------------------------------*/
3778
3779 /* Apply the artificial uses and defs at the end of BB in a backwards
3780    direction.  */
3781
3782 void
3783 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3784 {
3785   df_ref *def_rec;
3786   df_ref *use_rec;
3787   int bb_index = bb->index;
3788
3789   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3790     {
3791       df_ref def = *def_rec;
3792       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3793         bitmap_clear_bit (live, DF_REF_REGNO (def));
3794     }
3795
3796   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3797     {
3798       df_ref use = *use_rec;
3799       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3800         bitmap_set_bit (live, DF_REF_REGNO (use));
3801     }
3802 }
3803
3804
3805 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3806
3807 void
3808 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3809 {
3810   if (! INSN_P (insn))
3811     return;
3812
3813   df_simulate_defs (insn, live);
3814   df_simulate_uses (insn, live);
3815   df_simulate_fixup_sets (bb, live);
3816 }
3817
3818
3819 /* Apply the artificial uses and defs at the top of BB in a backwards
3820    direction.  */
3821
3822 void
3823 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3824 {
3825   df_ref *def_rec;
3826 #ifdef EH_USES
3827   df_ref *use_rec;
3828 #endif
3829   int bb_index = bb->index;
3830
3831   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3832     {
3833       df_ref def = *def_rec;
3834       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3835         bitmap_clear_bit (live, DF_REF_REGNO (def));
3836     }
3837
3838 #ifdef EH_USES
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)
3843         bitmap_set_bit (live, DF_REF_REGNO (use));
3844     }
3845 #endif
3846 }
3847 /*----------------------------------------------------------------------------
3848    The following three functions are used only for FORWARDS scanning:
3849    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3850    Thus it is important to add the DF_NOTES problem to the stack of
3851    problems computed before using these functions.
3852
3853    df_simulate_initialize_forwards should be called first with a
3854    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3855    df_simulate_one_insn_forwards should be called for each insn in
3856    the block, starting with the last on.  Finally,
3857    df_simulate_finalize_forwards can be called to get a new value
3858    of the sets at the bottom of the block (this is rarely used).
3859    ----------------------------------------------------------------------------*/
3860
3861 /* Apply the artificial uses and defs at the top of BB in a backwards
3862    direction.  */
3863
3864 void
3865 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3866 {
3867   df_ref *def_rec;
3868   int bb_index = bb->index;
3869
3870   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3871     {
3872       df_ref def = *def_rec;
3873       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3874         bitmap_clear_bit (live, DF_REF_REGNO (def));
3875     }
3876 }
3877
3878 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3879
3880 void
3881 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3882 {
3883   rtx link;
3884   if (! INSN_P (insn))
3885     return;
3886
3887   /* Make sure that the DF_NOTES really is an active df problem.  */
3888   gcc_assert (df_note);
3889
3890   df_simulate_defs (insn, live);
3891
3892   /* Clear all of the registers that go dead.  */
3893   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3894     {
3895       switch (REG_NOTE_KIND (link))
3896         {
3897         case REG_DEAD:
3898         case REG_UNUSED:
3899           {
3900             rtx reg = XEXP (link, 0);
3901             int regno = REGNO (reg);
3902             if (regno < FIRST_PSEUDO_REGISTER)
3903               {
3904                 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3905                 while (--n >= 0)
3906                   bitmap_clear_bit (live, regno + n);
3907               }
3908             else
3909               bitmap_clear_bit (live, regno);
3910           }
3911           break;
3912         default:
3913           break;
3914         }
3915     }
3916   df_simulate_fixup_sets (bb, live);
3917 }
3918
3919
3920 /* Apply the artificial uses and defs at the end of BB in a backwards
3921    direction.  */
3922
3923 void
3924 df_simulate_finalize_forwards (basic_block bb, bitmap live)
3925 {
3926   df_ref *def_rec;
3927   int bb_index = bb->index;
3928
3929   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3930     {
3931       df_ref def = *def_rec;
3932       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3933         bitmap_clear_bit (live, DF_REF_REGNO (def));
3934     }
3935 }
3936
3937
3938 \f
3939 /*----------------------------------------------------------------------------
3940    MULTIPLE DEFINITIONS
3941
3942    Find the locations in the function reached by multiple definition sites
3943    for a pseudo.  In and out bitvectors are built for each basic
3944    block.
3945
3946    The gen and kill sets for the problem are obvious.  Together they
3947    include all defined registers in a basic block; the gen set includes
3948    registers where a partial or conditional or may-clobber definition is
3949    last in the BB, while the kill set includes registers with a complete
3950    definition coming last.  However, the computation of the dataflow
3951    itself is interesting.
3952
3953    The idea behind it comes from SSA form's iterated dominance frontier
3954    criterion for inserting PHI functions.  Just like in that case, we can use
3955    the dominance frontier to find places where multiple definitions meet;
3956    a register X defined in a basic block BB1 has multiple definitions in
3957    basic blocks in BB1's dominance frontier.
3958
3959    So, the in-set of a basic block BB2 is not just the union of the
3960    out-sets of BB2's predecessors, but includes some more bits that come
3961    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3962    the previous paragraph).  I called this set the init-set of BB2.
3963
3964       (Note: I actually use the kill-set only to build the init-set.
3965       gen bits are anyway propagated from BB1 to BB2 by dataflow).
3966
3967     For example, if you have
3968
3969        BB1 : r10 = 0
3970              r11 = 0
3971              if <...> goto BB2 else goto BB3;
3972
3973        BB2 : r10 = 1
3974              r12 = 1
3975              goto BB3;
3976
3977        BB3 :
3978
3979     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3980     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
3981     not need to iterate the dominance frontier, because we do not insert
3982     anything like PHI functions there!  Instead, dataflow will take care of
3983     propagating the information to BB3's successors.
3984    ---------------------------------------------------------------------------*/
3985
3986 /* Scratch var used by transfer functions.  This is used to do md analysis
3987    only for live registers.  */
3988 static bitmap df_md_scratch;
3989
3990 /* Set basic block info.  */
3991
3992 static void
3993 df_md_set_bb_info (unsigned int index,
3994                    struct df_md_bb_info *bb_info)
3995 {
3996   gcc_assert (df_md);
3997   gcc_assert (index < df_md->block_info_size);
3998   df_md->block_info[index] = bb_info;
3999 }
4000
4001
4002 static void
4003 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4004                     void *vbb_info)
4005 {
4006   struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4007   if (bb_info)
4008     {
4009       BITMAP_FREE (bb_info->kill);
4010       BITMAP_FREE (bb_info->gen);
4011       BITMAP_FREE (bb_info->init);
4012       BITMAP_FREE (bb_info->in);
4013       BITMAP_FREE (bb_info->out);
4014       pool_free (df_md->block_pool, bb_info);
4015     }
4016 }
4017
4018
4019 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4020    not touched unless the block is new.  */
4021
4022 static void
4023 df_md_alloc (bitmap all_blocks)
4024 {
4025   unsigned int bb_index;
4026   bitmap_iterator bi;
4027
4028   if (!df_md->block_pool)
4029     df_md->block_pool = create_alloc_pool ("df_md_block pool",
4030                                            sizeof (struct df_md_bb_info), 50);
4031
4032   df_grow_bb_info (df_md);
4033   df_md_scratch = BITMAP_ALLOC (NULL);
4034
4035   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4036     {
4037       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4038       if (bb_info)
4039         {
4040           bitmap_clear (bb_info->init);
4041           bitmap_clear (bb_info->gen);
4042           bitmap_clear (bb_info->kill);
4043           bitmap_clear (bb_info->in);
4044           bitmap_clear (bb_info->out);
4045         }
4046       else
4047         {
4048           bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
4049           df_md_set_bb_info (bb_index, bb_info);
4050           bb_info->init = BITMAP_ALLOC (NULL);
4051           bb_info->gen = BITMAP_ALLOC (NULL);
4052           bb_info->kill = BITMAP_ALLOC (NULL);
4053           bb_info->in = BITMAP_ALLOC (NULL);
4054           bb_info->out = BITMAP_ALLOC (NULL);
4055         }
4056     }
4057
4058   df_md->optional_p = true;
4059 }
4060
4061 /* Add the effect of the top artificial defs of BB to the multiple definitions
4062    bitmap LOCAL_MD.  */
4063
4064 void
4065 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4066 {
4067   int bb_index = bb->index;
4068   df_ref *def_rec;
4069   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4070     {
4071       df_ref def = *def_rec;
4072       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4073         {
4074           unsigned int dregno = DF_REF_REGNO (def);
4075           if (DF_REF_FLAGS (def)
4076               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4077             bitmap_set_bit (local_md, dregno);
4078           else
4079             bitmap_clear_bit (local_md, dregno);
4080         }
4081     }
4082 }
4083
4084
4085 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4086    LOCAL_MD.  */
4087
4088 void
4089 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
4090                         bitmap local_md)
4091 {
4092   unsigned uid = INSN_UID (insn);
4093   df_ref *def_rec;
4094
4095   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4096     {
4097       df_ref def = *def_rec;
4098       unsigned int dregno = DF_REF_REGNO (def);
4099       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4100           || (dregno >= FIRST_PSEUDO_REGISTER))
4101         {
4102           if (DF_REF_FLAGS (def)
4103               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4104            bitmap_set_bit (local_md, DF_REF_ID (def));
4105          else
4106            bitmap_clear_bit (local_md, DF_REF_ID (def));
4107         }
4108     }
4109 }
4110
4111 static void
4112 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4113                                     df_ref *def_rec,
4114                                     int top_flag)
4115 {
4116   df_ref def;
4117   bitmap_clear (seen_in_insn);
4118
4119   while ((def = *def_rec++) != NULL)
4120     {
4121       unsigned int dregno = DF_REF_REGNO (def);
4122       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4123             || (dregno >= FIRST_PSEUDO_REGISTER))
4124           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4125         {
4126           if (!bitmap_bit_p (seen_in_insn, dregno))
4127             {
4128               if (DF_REF_FLAGS (def)
4129                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4130                 {
4131                   bitmap_set_bit (bb_info->gen, dregno);
4132                   bitmap_clear_bit (bb_info->kill, dregno);
4133                 }
4134               else
4135                 {
4136                   /* When we find a clobber and a regular def,
4137                      make sure the regular def wins.  */
4138                   bitmap_set_bit (seen_in_insn, dregno);
4139                   bitmap_set_bit (bb_info->kill, dregno);
4140                   bitmap_clear_bit (bb_info->gen, dregno);
4141                 }
4142             }
4143         }
4144     }
4145 }
4146
4147
4148 /* Compute local multiple def info for basic block BB.  */
4149
4150 static void
4151 df_md_bb_local_compute (unsigned int bb_index)
4152 {
4153   basic_block bb = BASIC_BLOCK (bb_index);
4154   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4155   rtx insn;
4156
4157   /* Artificials are only hard regs.  */
4158   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4159     df_md_bb_local_compute_process_def (bb_info,
4160                                         df_get_artificial_defs (bb_index),
4161                                         DF_REF_AT_TOP);
4162
4163   FOR_BB_INSNS (bb, insn)
4164     {
4165       unsigned int uid = INSN_UID (insn);
4166       if (!INSN_P (insn))
4167         continue;
4168
4169       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4170     }
4171
4172   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4173     df_md_bb_local_compute_process_def (bb_info,
4174                                         df_get_artificial_defs (bb_index),
4175                                         0);
4176 }
4177
4178 /* Compute local reaching def info for each basic block within BLOCKS.  */
4179
4180 static void
4181 df_md_local_compute (bitmap all_blocks)
4182 {
4183   unsigned int bb_index, df_bb_index;
4184   bitmap_iterator bi1, bi2;
4185   basic_block bb;
4186   bitmap *frontiers;
4187
4188   seen_in_insn = BITMAP_ALLOC (NULL);
4189
4190   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4191     {
4192       df_md_bb_local_compute (bb_index);
4193     }
4194
4195   BITMAP_FREE (seen_in_insn);
4196
4197   frontiers = XNEWVEC (bitmap, last_basic_block);
4198   FOR_ALL_BB (bb)
4199     frontiers[bb->index] = BITMAP_ALLOC (NULL);
4200
4201   compute_dominance_frontiers (frontiers);
4202
4203   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
4204   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4205     {
4206       bitmap kill = df_md_get_bb_info (bb_index)->kill;
4207       EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
4208         {
4209           basic_block bb = BASIC_BLOCK (df_bb_index);
4210           if (bitmap_bit_p (all_blocks, df_bb_index))
4211             bitmap_ior_and_into (df_md_get_bb_info (df_bb_index)->init, kill,
4212                                  df_get_live_in (bb));
4213         }
4214     }
4215
4216   FOR_ALL_BB (bb)
4217     BITMAP_FREE (frontiers[bb->index]);
4218   free (frontiers);
4219 }
4220
4221
4222 /* Reset the global solution for recalculation.  */
4223
4224 static void
4225 df_md_reset (bitmap all_blocks)
4226 {
4227   unsigned int bb_index;
4228   bitmap_iterator bi;
4229
4230   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4231     {
4232       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4233       gcc_assert (bb_info);
4234       bitmap_clear (bb_info->in);
4235       bitmap_clear (bb_info->out);
4236     }
4237 }
4238
4239 static bool
4240 df_md_transfer_function (int bb_index)
4241 {
4242   basic_block bb = BASIC_BLOCK (bb_index);
4243   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4244   bitmap in = bb_info->in;
4245   bitmap out = bb_info->out;
4246   bitmap gen = bb_info->gen;
4247   bitmap kill = bb_info->kill;
4248
4249   /* We need to use a scratch set here so that the value returned from
4250      this function invocation properly reflects if the sets changed in
4251      a significant way; i.e. not just because the live set was anded
4252      in.  */
4253   bitmap_and (df_md_scratch, gen, df_get_live_out (bb));
4254
4255   /* Multiple definitions of a register are not relevant if it is not
4256      used.  Thus we trim the result to the places where it is live.  */
4257   bitmap_and_into (in, df_get_live_in (bb));
4258
4259   return bitmap_ior_and_compl (out, df_md_scratch, in, kill);
4260 }
4261
4262 /* Initialize the solution bit vectors for problem.  */
4263
4264 static void
4265 df_md_init (bitmap all_blocks)
4266 {
4267   unsigned int bb_index;
4268   bitmap_iterator bi;
4269
4270   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4271     {
4272       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4273
4274       bitmap_copy (bb_info->in, bb_info->init);
4275       df_md_transfer_function (bb_index);
4276     }
4277 }
4278
4279 static void
4280 df_md_confluence_0 (basic_block bb)
4281 {
4282   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4283   bitmap_copy (bb_info->in, bb_info->init);
4284 }
4285
4286 /* In of target gets or of out of source.  */
4287
4288 static void
4289 df_md_confluence_n (edge e)
4290 {
4291   bitmap op1 = df_md_get_bb_info (e->dest->index)->in;
4292   bitmap op2 = df_md_get_bb_info (e->src->index)->out;
4293
4294   if (e->flags & EDGE_FAKE)
4295     return;
4296
4297   if (e->flags & EDGE_EH)
4298     bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
4299   else
4300     bitmap_ior_into (op1, op2);
4301 }
4302
4303 /* Free all storage associated with the problem.  */
4304
4305 static void
4306 df_md_free (void)
4307 {
4308   unsigned int i;
4309   for (i = 0; i < df_md->block_info_size; i++)
4310     {
4311       struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
4312       if (bb_info)
4313         {
4314           BITMAP_FREE (bb_info->kill);
4315           BITMAP_FREE (bb_info->gen);
4316           BITMAP_FREE (bb_info->init);
4317           BITMAP_FREE (bb_info->in);
4318           BITMAP_FREE (bb_info->out);
4319         }
4320     }
4321
4322   BITMAP_FREE (df_md_scratch);
4323   free_alloc_pool (df_md->block_pool);
4324
4325   df_md->block_info_size = 0;
4326   free (df_md->block_info);
4327   free (df_md);
4328 }
4329
4330
4331 /* Debugging info at top of bb.  */
4332
4333 static void
4334 df_md_top_dump (basic_block bb, FILE *file)
4335 {
4336   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4337   if (!bb_info || !bb_info->in)
4338     return;
4339
4340   fprintf (file, ";; md  in  \t");
4341   df_print_regset (file, bb_info->in);
4342   fprintf (file, ";; md  init  \t");
4343   df_print_regset (file, bb_info->init);
4344   fprintf (file, ";; md  gen \t");
4345   df_print_regset (file, bb_info->gen);
4346   fprintf (file, ";; md  kill \t");
4347   df_print_regset (file, bb_info->kill);
4348 }
4349
4350 /* Debugging info at bottom of bb.  */
4351
4352 static void
4353 df_md_bottom_dump (basic_block bb, FILE *file)
4354 {
4355   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4356   if (!bb_info || !bb_info->out)
4357     return;
4358
4359   fprintf (file, ";; md  out \t");
4360   df_print_regset (file, bb_info->out);
4361 }
4362
4363 static struct df_problem problem_MD =
4364 {
4365   DF_MD,                      /* Problem id.  */
4366   DF_FORWARD,                 /* Direction.  */
4367   df_md_alloc,                /* Allocate the problem specific data.  */
4368   df_md_reset,                /* Reset global information.  */
4369   df_md_free_bb_info,         /* Free basic block info.  */
4370   df_md_local_compute,        /* Local compute function.  */
4371   df_md_init,                 /* Init the solution specific data.  */
4372   df_worklist_dataflow,       /* Worklist solver.  */
4373   df_md_confluence_0,         /* Confluence operator 0.  */
4374   df_md_confluence_n,         /* Confluence operator n.  */
4375   df_md_transfer_function,    /* Transfer function.  */
4376   NULL,                       /* Finalize function.  */
4377   df_md_free,                 /* Free all of the problem information.  */
4378   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4379   NULL,                       /* Debugging.  */
4380   df_md_top_dump,             /* Debugging start block.  */
4381   df_md_bottom_dump,          /* Debugging end block.  */
4382   NULL,                       /* Incremental solution verify start.  */
4383   NULL,                       /* Incremental solution verify end.  */
4384   NULL,                       /* Dependent problem.  */
4385   TV_DF_MD,                   /* Timing variable.  */
4386   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4387 };
4388
4389 /* Create a new MD instance and add it to the existing instance
4390    of DF.  */
4391
4392 void
4393 df_md_add_problem (void)
4394 {
4395   df_add_problem (&problem_MD);
4396 }
4397
4398
4399