gcc/df-problems.c

   1 /* Standard problems for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
   3    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 = xrealloc (dflow->block_info,
 113                                     new_size *sizeof (void*));
 114       memset (dflow->block_info + dflow->block_info_size, 0,
 115               (new_size - dflow->block_info_size) *sizeof (void *));
 116       dflow->block_info_size = new_size;
 117     }
 118 }
 119
 120 /* Dump a def-use or use-def chain for REF to FILE.  */
 121
 122 void
 123 df_chain_dump (struct df_link *link, FILE *file)
 124 {
 125   fprintf (file, "{ ");
 126   for (; link; link = link->next)
 127     {
 128       fprintf (file, "%c%d(bb %d insn %d) ",
 129                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
 130                DF_REF_ID (link->ref),
 131                DF_REF_BBNO (link->ref),
 132                DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
 133     }
 134   fprintf (file, "}");
 135 }
 136
 137
 138 /* Print some basic block info as part of df_dump.  */
 139
 140 void
 141 df_print_bb_index (basic_block bb, FILE *file)
 142 {
 143   edge e;
 144   edge_iterator ei;
 145
 146   fprintf (file, "\n( ");
 147     FOR_EACH_EDGE (e, ei, bb->preds)
 148     {
 149       basic_block pred = e->src;
 150       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
 151     }
 152   fprintf (file, ")->[%d]->( ", bb->index);
 153   FOR_EACH_EDGE (e, ei, bb->succs)
 154     {
 155       basic_block succ = e->dest;
 156       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
 157     }
 158   fprintf (file, ")\n");
 159 }
 160
 161
 162
 163 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
 164    up correctly. */
 165
 166 static void
 167 df_set_seen (void)
 168 {
 169   seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
 170   seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
 171 }
 172
 173
 174 static void
 175 df_unset_seen (void)
 176 {
 177   BITMAP_FREE (seen_in_block);
 178   BITMAP_FREE (seen_in_insn);
 179 }
 180
 181
 182 \f
 183 /*----------------------------------------------------------------------------
 184    REACHING DEFINITIONS
 185
 186    Find the locations in the function where each definition site for a
 187    pseudo reaches.  In and out bitvectors are built for each basic
 188    block.  The id field in the ref is used to index into these sets.
 189    See df.h for details.
 190    ----------------------------------------------------------------------------*/
 191
 192 /* This problem plays a large number of games for the sake of
 193    efficiency.
 194
 195    1) The order of the bits in the bitvectors.  After the scanning
 196    phase, all of the defs are sorted.  All of the defs for the reg 0
 197    are first, followed by all defs for reg 1 and so on.
 198
 199    2) There are two kill sets, one if the number of defs is less or
 200    equal to DF_SPARSE_THRESHOLD and another if the number of defs is
 201    greater.
 202
 203    <= : Data is built directly in the kill set.
 204
 205    > : One level of indirection is used to keep from generating long
 206    strings of 1 bits in the kill sets.  Bitvectors that are indexed
 207    by the regnum are used to represent that there is a killing def
 208    for the register.  The confluence and transfer functions use
 209    these along with the bitmap_clear_range call to remove ranges of
 210    bits without actually generating a knockout vector.
 211
 212    The kill and sparse_kill and the dense_invalidated_by_call and
 213    sparse_invalidated_by_call both play this game.  */
 214
 215 /* Private data used to compute the solution for this problem.  These
 216    data structures are not accessible outside of this module.  */
 217 struct df_rd_problem_data
 218 {
 219   /* The set of defs to regs invalidated by call.  */
 220   bitmap sparse_invalidated_by_call;
 221   /* The set of defs to regs invalidate by call for rd.  */
 222   bitmap dense_invalidated_by_call;
 223   /* An obstack for the bitmaps we need for this problem.  */
 224   bitmap_obstack rd_bitmaps;
 225 };
 226
 227 /* Set basic block info.  */
 228
 229 static void
 230 df_rd_set_bb_info (unsigned int index,
 231                    struct df_rd_bb_info *bb_info)
 232 {
 233   gcc_assert (df_rd);
 234   gcc_assert (index < df_rd->block_info_size);
 235   df_rd->block_info[index] = bb_info;
 236 }
 237
 238
 239 /* Free basic block info.  */
 240
 241 static void
 242 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 243                     void *vbb_info)
 244 {
 245   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
 246   if (bb_info)
 247     {
 248       if (bb_info->expanded_lr_out)
 249         BITMAP_FREE (bb_info->expanded_lr_out);
 250       BITMAP_FREE (bb_info->kill);
 251       BITMAP_FREE (bb_info->sparse_kill);
 252       BITMAP_FREE (bb_info->gen);
 253       BITMAP_FREE (bb_info->in);
 254       BITMAP_FREE (bb_info->out);
 255       pool_free (df_rd->block_pool, bb_info);
 256     }
 257 }
 258
 259
 260 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
 261    not touched unless the block is new.  */
 262
 263 static void
 264 df_rd_alloc (bitmap all_blocks)
 265 {
 266   unsigned int bb_index;
 267   bitmap_iterator bi;
 268   struct df_rd_problem_data *problem_data;
 269
 270   if (!df_rd->block_pool)
 271     df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
 272                                            sizeof (struct df_rd_bb_info), 50);
 273
 274   if (df_rd->problem_data)
 275     {
 276       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 277       bitmap_clear (problem_data->sparse_invalidated_by_call);
 278       bitmap_clear (problem_data->dense_invalidated_by_call);
 279     }
 280   else
 281     {
 282       problem_data = XNEW (struct df_rd_problem_data);
 283       df_rd->problem_data = problem_data;
 284
 285       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
 286       problem_data->sparse_invalidated_by_call
 287         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 288       problem_data->dense_invalidated_by_call
 289         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 290     }
 291
 292   df_grow_bb_info (df_rd);
 293
 294   /* Because of the clustering of all use sites for the same pseudo,
 295      we have to process all of the blocks before doing the
 296      analysis.  */
 297
 298   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 299     {
 300       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 301       if (bb_info)
 302         {
 303           if (bb_info->expanded_lr_out)
 304             bitmap_clear (bb_info->expanded_lr_out);
 305           bitmap_clear (bb_info->kill);
 306           bitmap_clear (bb_info->sparse_kill);
 307           bitmap_clear (bb_info->gen);
 308         }
 309       else
 310         {
 311           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
 312           df_rd_set_bb_info (bb_index, bb_info);
 313           if (df->changeable_flags & DF_RD_NO_TRIM)
 314             bb_info->expanded_lr_out = NULL;
 315           else
 316             bb_info->expanded_lr_out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 317           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 318           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 319           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 320           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 321           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 322         }
 323     }
 324   df_rd->optional_p = true;
 325 }
 326
 327
 328 /* Process a list of DEFs for df_rd_bb_local_compute.  */
 329
 330 static void
 331 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
 332                                     struct df_ref **def_rec,
 333                                     enum df_ref_flags top_flag)
 334 {
 335   for (; *def_rec; def_rec++)
 336     {
 337       struct df_ref *def = *def_rec;
 338       unsigned int regno = DF_REF_REGNO (def);
 339
 340       /* This makes sure we do the artificial defs in the right order
 341          since they are all in the same list.  */
 342       if (top_flag != (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
 343         continue;
 344
 345       /* Skip over the hard regs if we do not care about them.  */
 346       if ((df->changeable_flags & DF_NO_HARD_REGS) &&
 347           (regno < FIRST_PSEUDO_REGISTER))
 348         continue;
 349
 350       /* Only the last def(s) for a regno in the block has any
 351          effect.  */
 352       if (bitmap_bit_p (seen_in_block, regno))
 353         continue;
 354
 355       /* The first def for regno in insn gets to knock out the
 356          defs from other instructions.  */
 357       if ((!bitmap_bit_p (seen_in_insn, regno))
 358           /* If the def is to only part of the reg, it does
 359              not kill the other defs that reach here.  */
 360           && (!(DF_REF_FLAGS (def) &
 361                 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
 362         {
 363           unsigned int begin = DF_DEFS_BEGIN (regno);
 364           unsigned int n_defs = DF_DEFS_COUNT (regno);
 365           if (n_defs > DF_SPARSE_THRESHOLD)
 366             bitmap_set_bit (bb_info->sparse_kill, regno);
 367           else
 368             bitmap_set_range (bb_info->kill, begin, n_defs);
 369           bitmap_clear_range(bb_info->gen, begin, n_defs);
 370         }
 371
 372       bitmap_set_bit (seen_in_insn, regno);
 373       /* All defs for regno in the instruction may be put into
 374          the gen set.  */
 375       if (!(DF_REF_FLAGS (def)
 376             & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
 377         bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
 378     }
 379 }
 380
 381 /* Compute local reaching def info for basic block BB.  */
 382
 383 static void
 384 df_rd_bb_local_compute (unsigned int bb_index)
 385 {
 386   basic_block bb = BASIC_BLOCK (bb_index);
 387   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 388   struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
 389   rtx insn;
 390
 391   bitmap_clear (seen_in_block);
 392   bitmap_clear (seen_in_insn);
 393
 394   if (!(df->changeable_flags & DF_RD_NO_TRIM))
 395     {
 396       unsigned int regno;
 397       bitmap_iterator bi;
 398       int first_reg = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
 399       EXECUTE_IF_SET_IN_BITMAP (lr_bb_info->out, first_reg, regno, bi)
 400         {
 401           unsigned int begin = DF_DEFS_BEGIN (regno);
 402           unsigned int n_defs = DF_DEFS_COUNT (regno);
 403           bitmap_set_range (bb_info->expanded_lr_out, begin, n_defs);
 404         }
 405     }
 406
 407   /* Artificials are only hard regs.  */
 408   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 409     df_rd_bb_local_compute_process_def (bb_info,
 410                                         df_get_artificial_defs (bb_index),
 411                                         0);
 412
 413   FOR_BB_INSNS_REVERSE (bb, insn)
 414     {
 415       unsigned int uid = INSN_UID (insn);
 416
 417       if (!INSN_P (insn))
 418         continue;
 419
 420       df_rd_bb_local_compute_process_def (bb_info,
 421                                           DF_INSN_UID_DEFS (uid), 0);
 422
 423       /* This complex dance with the two bitmaps is required because
 424          instructions can assign twice to the same pseudo.  This
 425          generally happens with calls that will have one def for the
 426          result and another def for the clobber.  If only one vector
 427          is used and the clobber goes first, the result will be
 428          lost.  */
 429       bitmap_ior_into (seen_in_block, seen_in_insn);
 430       bitmap_clear (seen_in_insn);
 431     }
 432
 433   /* Process the artificial defs at the top of the block last since we
 434      are going backwards through the block and these are logically at
 435      the start.  */
 436   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 437     df_rd_bb_local_compute_process_def (bb_info,
 438                                         df_get_artificial_defs (bb_index),
 439                                         DF_REF_AT_TOP);
 440 }
 441
 442
 443 /* Compute local reaching def info for each basic block within BLOCKS.  */
 444
 445 static void
 446 df_rd_local_compute (bitmap all_blocks)
 447 {
 448   unsigned int bb_index;
 449   bitmap_iterator bi;
 450   unsigned int regno;
 451   struct df_rd_problem_data *problem_data
 452     = (struct df_rd_problem_data *) df_rd->problem_data;
 453   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 454   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 455
 456   df_set_seen ();
 457
 458   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
 459
 460   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 461     {
 462       df_rd_bb_local_compute (bb_index);
 463     }
 464
 465   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
 466   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
 467     {
 468       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
 469         bitmap_set_bit (sparse_invalidated, regno);
 470       else
 471         bitmap_set_range (dense_invalidated,
 472                           DF_DEFS_BEGIN (regno),
 473                           DF_DEFS_COUNT (regno));
 474     }
 475   df_unset_seen ();
 476 }
 477
 478
 479 /* Initialize the solution bit vectors for problem.  */
 480
 481 static void
 482 df_rd_init_solution (bitmap all_blocks)
 483 {
 484   unsigned int bb_index;
 485   bitmap_iterator bi;
 486
 487   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 488     {
 489       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 490
 491       bitmap_copy (bb_info->out, bb_info->gen);
 492       bitmap_clear (bb_info->in);
 493     }
 494 }
 495
 496 /* In of target gets or of out of source.  */
 497
 498 static void
 499 df_rd_confluence_n (edge e)
 500 {
 501   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
 502   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
 503
 504   if (e->flags & EDGE_FAKE)
 505     return;
 506
 507   /* If we are trimming the solution, the invalidated_by_call code in
 508      the lr problem makes this unnecessary.  However, if we do not
 509      trim, we must take this into account.  */
 510   if ((df->changeable_flags & DF_RD_NO_TRIM) && e->flags & EDGE_EH)
 511     {
 512       struct df_rd_problem_data *problem_data
 513         = (struct df_rd_problem_data *) df_rd->problem_data;
 514       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 515       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 516       bitmap_iterator bi;
 517       unsigned int regno;
 518       bitmap tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 519
 520       bitmap_copy (tmp, op2);
 521       bitmap_and_compl_into (tmp, dense_invalidated);
 522
 523       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
 524         {
 525           bitmap_clear_range (tmp,
 526                               DF_DEFS_BEGIN (regno),
 527                               DF_DEFS_COUNT (regno));
 528         }
 529       bitmap_ior_into (op1, tmp);
 530       BITMAP_FREE (tmp);
 531     }
 532   else
 533     bitmap_ior_into (op1, op2);
 534 }
 535
 536
 537 /* Transfer function.  */
 538
 539 static bool
 540 df_rd_transfer_function (int bb_index)
 541 {
 542   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 543   unsigned int regno;
 544   bitmap_iterator bi;
 545   bitmap in = bb_info->in;
 546   bitmap out = bb_info->out;
 547   bitmap gen = bb_info->gen;
 548   bitmap kill = bb_info->kill;
 549   bitmap sparse_kill = bb_info->sparse_kill;
 550   bool changed = false;
 551
 552   if ((df->changeable_flags & DF_RD_NO_TRIM) && bitmap_empty_p (sparse_kill))
 553     changed = bitmap_ior_and_compl (out, gen, in, kill);
 554   else
 555     {
 556       struct df_rd_problem_data *problem_data;
 557       bitmap tmp;
 558
 559       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
 560          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
 561       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 562       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 563
 564       bitmap_copy (tmp, in);
 565       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
 566         {
 567           bitmap_clear_range (tmp,
 568                               DF_DEFS_BEGIN (regno),
 569                               DF_DEFS_COUNT (regno));
 570         }
 571       bitmap_and_compl_into (tmp, kill);
 572       bitmap_ior_into (tmp, gen);
 573       if (!(df->changeable_flags & DF_RD_NO_TRIM))
 574         bitmap_and_into (tmp, bb_info->expanded_lr_out);
 575       changed = !bitmap_equal_p (tmp, out);
 576       if (changed)
 577         {
 578           BITMAP_FREE (out);
 579           bb_info->out = tmp;
 580         }
 581       else
 582         BITMAP_FREE (tmp);
 583     }
 584
 585   return changed;
 586 }
 587
 588
 589 /* Free all storage associated with the problem.  */
 590
 591 static void
 592 df_rd_free (void)
 593 {
 594   unsigned int i;
 595   struct df_rd_problem_data *problem_data
 596     = (struct df_rd_problem_data *) df_rd->problem_data;
 597
 598   if (problem_data)
 599     {
 600       for (i = 0; i < df_rd->block_info_size; i++)
 601         {
 602           struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
 603           if (bb_info)
 604             {
 605               if (bb_info->expanded_lr_out)
 606                 BITMAP_FREE (bb_info->expanded_lr_out);
 607               BITMAP_FREE (bb_info->kill);
 608               BITMAP_FREE (bb_info->sparse_kill);
 609               BITMAP_FREE (bb_info->gen);
 610               BITMAP_FREE (bb_info->in);
 611               BITMAP_FREE (bb_info->out);
 612             }
 613         }
 614
 615       free_alloc_pool (df_rd->block_pool);
 616       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
 617       BITMAP_FREE (problem_data->dense_invalidated_by_call);
 618       bitmap_obstack_release (&problem_data->rd_bitmaps);
 619
 620       df_rd->block_info_size = 0;
 621       free (df_rd->block_info);
 622       free (df_rd->problem_data);
 623     }
 624   free (df_rd);
 625 }
 626
 627
 628 /* Debugging info.  */
 629
 630 static void
 631 df_rd_start_dump (FILE *file)
 632 {
 633   struct df_rd_problem_data *problem_data
 634     = (struct df_rd_problem_data *) df_rd->problem_data;
 635   unsigned int m = DF_REG_SIZE(df);
 636   unsigned int regno;
 637
 638   if (!df_rd->block_info)
 639     return;
 640
 641   fprintf (file, ";; Reaching defs:\n\n");
 642
 643   fprintf (file, "  sparse invalidated \t");
 644   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
 645   fprintf (file, "  dense invalidated \t");
 646   dump_bitmap (file, problem_data->dense_invalidated_by_call);
 647
 648   for (regno = 0; regno < m; regno++)
 649     if (DF_DEFS_COUNT (regno))
 650       fprintf (file, "%d[%d,%d] ", regno,
 651                DF_DEFS_BEGIN (regno),
 652                DF_DEFS_COUNT (regno));
 653   fprintf (file, "\n");
 654
 655 }
 656
 657
 658 /* Debugging info at top of bb.  */
 659
 660 static void
 661 df_rd_top_dump (basic_block bb, FILE *file)
 662 {
 663   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 664   if (!bb_info || !bb_info->in)
 665     return;
 666
 667   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
 668   dump_bitmap (file, bb_info->in);
 669   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
 670   dump_bitmap (file, bb_info->gen);
 671   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
 672   dump_bitmap (file, bb_info->kill);
 673 }
 674
 675
 676 /* Debugging info at top of bb.  */
 677
 678 static void
 679 df_rd_bottom_dump (basic_block bb, FILE *file)
 680 {
 681   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 682   if (!bb_info || !bb_info->out)
 683     return;
 684
 685   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
 686   dump_bitmap (file, bb_info->out);
 687 }
 688
 689 /* All of the information associated with every instance of the problem.  */
 690
 691 static struct df_problem problem_RD =
 692 {
 693   DF_RD,                      /* Problem id.  */
 694   DF_FORWARD,                 /* Direction.  */
 695   df_rd_alloc,                /* Allocate the problem specific data.  */
 696   NULL,                       /* Reset global information.  */
 697   df_rd_free_bb_info,         /* Free basic block info.  */
 698   df_rd_local_compute,        /* Local compute function.  */
 699   df_rd_init_solution,        /* Init the solution specific data.  */
 700   df_worklist_dataflow,       /* Worklist solver.  */
 701   NULL,                       /* Confluence operator 0.  */
 702   df_rd_confluence_n,         /* Confluence operator n.  */
 703   df_rd_transfer_function,    /* Transfer function.  */
 704   NULL,                       /* Finalize function.  */
 705   df_rd_free,                 /* Free all of the problem information.  */
 706   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
 707   df_rd_start_dump,           /* Debugging.  */
 708   df_rd_top_dump,             /* Debugging start block.  */
 709   df_rd_bottom_dump,          /* Debugging end block.  */
 710   NULL,                       /* Incremental solution verify start.  */
 711   NULL,                       /* Incremental solution verify end.  */
 712   NULL,                       /* Dependent problem.  */
 713   TV_DF_RD,                   /* Timing variable.  */
 714   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 715 };
 716
 717
 718
 719 /* Create a new DATAFLOW instance and add it to an existing instance
 720    of DF.  The returned structure is what is used to get at the
 721    solution.  */
 722
 723 void
 724 df_rd_add_problem (void)
 725 {
 726   df_add_problem (&problem_RD);
 727 }
 728
 729
 730 \f
 731 /*----------------------------------------------------------------------------
 732    LIVE REGISTERS
 733
 734    Find the locations in the function where any use of a pseudo can
 735    reach in the backwards direction.  In and out bitvectors are built
 736    for each basic block.  The regnum is used to index into these sets.
 737    See df.h for details.
 738    ----------------------------------------------------------------------------*/
 739
 740 /* Private data used to verify the solution for this problem.  */
 741 struct df_lr_problem_data
 742 {
 743   bitmap *in;
 744   bitmap *out;
 745 };
 746
 747
 748 /* Set basic block info.  */
 749
 750 static void
 751 df_lr_set_bb_info (unsigned int index,
 752                    struct df_lr_bb_info *bb_info)
 753 {
 754   gcc_assert (df_lr);
 755   gcc_assert (index < df_lr->block_info_size);
 756   df_lr->block_info[index] = bb_info;
 757 }
 758
 759
 760 /* Free basic block info.  */
 761
 762 static void
 763 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 764                     void *vbb_info)
 765 {
 766   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
 767   if (bb_info)
 768     {
 769       BITMAP_FREE (bb_info->use);
 770       BITMAP_FREE (bb_info->def);
 771       BITMAP_FREE (bb_info->in);
 772       BITMAP_FREE (bb_info->out);
 773       pool_free (df_lr->block_pool, bb_info);
 774     }
 775 }
 776
 777
 778 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
 779    not touched unless the block is new.  */
 780
 781 static void
 782 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 783 {
 784   unsigned int bb_index;
 785   bitmap_iterator bi;
 786
 787   if (!df_lr->block_pool)
 788     df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
 789                                            sizeof (struct df_lr_bb_info), 50);
 790
 791   df_grow_bb_info (df_lr);
 792
 793   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 794     {
 795       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 796       if (bb_info)
 797         {
 798           bitmap_clear (bb_info->def);
 799           bitmap_clear (bb_info->use);
 800         }
 801       else
 802         {
 803           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
 804           df_lr_set_bb_info (bb_index, bb_info);
 805           bb_info->use = BITMAP_ALLOC (NULL);
 806           bb_info->def = BITMAP_ALLOC (NULL);
 807           bb_info->in = BITMAP_ALLOC (NULL);
 808           bb_info->out = BITMAP_ALLOC (NULL);
 809         }
 810     }
 811
 812   df_lr->optional_p = false;
 813 }
 814
 815
 816 /* Reset the global solution for recalculation.  */
 817
 818 static void
 819 df_lr_reset (bitmap all_blocks)
 820 {
 821   unsigned int bb_index;
 822   bitmap_iterator bi;
 823
 824   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 825     {
 826       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 827       gcc_assert (bb_info);
 828       bitmap_clear (bb_info->in);
 829       bitmap_clear (bb_info->out);
 830     }
 831 }
 832
 833
 834 /* Compute local live register info for basic block BB.  */
 835
 836 static void
 837 df_lr_bb_local_compute (unsigned int bb_index)
 838 {
 839   basic_block bb = BASIC_BLOCK (bb_index);
 840   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 841   rtx insn;
 842   struct df_ref **def_rec;
 843   struct df_ref **use_rec;
 844
 845   /* Process the registers set in an exception handler.  */
 846   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 847     {
 848       struct df_ref *def = *def_rec;
 849       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 850         {
 851           unsigned int dregno = DF_REF_REGNO (def);
 852           bitmap_set_bit (bb_info->def, dregno);
 853           bitmap_clear_bit (bb_info->use, dregno);
 854         }
 855     }
 856
 857   /* Process the hardware registers that are always live.  */
 858   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 859     {
 860       struct df_ref *use = *use_rec;
 861       /* Add use to set of uses in this BB.  */
 862       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 863         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 864     }
 865
 866   FOR_BB_INSNS_REVERSE (bb, insn)
 867     {
 868       unsigned int uid = INSN_UID (insn);
 869
 870       if (!INSN_P (insn))
 871         continue;
 872
 873       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 874         {
 875           struct df_ref *def = *def_rec;
 876           /* If the def is to only part of the reg, it does
 877              not kill the other defs that reach here.  */
 878           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 879             {
 880               unsigned int dregno = DF_REF_REGNO (def);
 881               bitmap_set_bit (bb_info->def, dregno);
 882               bitmap_clear_bit (bb_info->use, dregno);
 883             }
 884         }
 885
 886       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 887         {
 888           struct df_ref *use = *use_rec;
 889           /* Add use to set of uses in this BB.  */
 890           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 891         }
 892     }
 893
 894   /* Process the registers set in an exception handler or the hard
 895      frame pointer if this block is the target of a non local
 896      goto.  */
 897   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 898     {
 899       struct df_ref *def = *def_rec;
 900       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 901         {
 902           unsigned int dregno = DF_REF_REGNO (def);
 903           bitmap_set_bit (bb_info->def, dregno);
 904           bitmap_clear_bit (bb_info->use, dregno);
 905         }
 906     }
 907
 908 #ifdef EH_USES
 909   /* Process the uses that are live into an exception handler.  */
 910   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 911     {
 912       struct df_ref *use = *use_rec;
 913       /* Add use to set of uses in this BB.  */
 914       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 915         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 916     }
 917 #endif
 918
 919   /* If the df_live problem is not defined, such as at -O0 and -O1, we
 920      still need to keep the luids up to date.  This is normally done
 921      in the df_live problem since this problem has a forwards
 922      scan.  */
 923   if (!df_live)
 924     df_recompute_luids (bb);
 925 }
 926
 927
 928 /* Compute local live register info for each basic block within BLOCKS.  */
 929
 930 static void
 931 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
 932 {
 933   unsigned int bb_index;
 934   bitmap_iterator bi;
 935
 936   bitmap_clear (df->hardware_regs_used);
 937
 938   /* The all-important stack pointer must always be live.  */
 939   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
 940
 941   /* Before reload, there are a few registers that must be forced
 942      live everywhere -- which might not already be the case for
 943      blocks within infinite loops.  */
 944   if (!reload_completed)
 945     {
 946       /* Any reference to any pseudo before reload is a potential
 947          reference of the frame pointer.  */
 948       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
 949
 950 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
 951       /* Pseudos with argument area equivalences may require
 952          reloading via the argument pointer.  */
 953       if (fixed_regs[ARG_POINTER_REGNUM])
 954         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
 955 #endif
 956
 957       /* Any constant, or pseudo with constant equivalences, may
 958          require reloading from memory using the pic register.  */
 959       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
 960           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
 961         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
 962     }
 963
 964   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 965     {
 966       if (bb_index == EXIT_BLOCK)
 967         {
 968           /* The exit block is special for this problem and its bits are
 969              computed from thin air.  */
 970           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
 971           bitmap_copy (bb_info->use, df->exit_block_uses);
 972         }
 973       else
 974         df_lr_bb_local_compute (bb_index);
 975     }
 976
 977   bitmap_clear (df_lr->out_of_date_transfer_functions);
 978 }
 979
 980
 981 /* Initialize the solution vectors.  */
 982
 983 static void
 984 df_lr_init (bitmap all_blocks)
 985 {
 986   unsigned int bb_index;
 987   bitmap_iterator bi;
 988
 989   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 990     {
 991       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 992       bitmap_copy (bb_info->in, bb_info->use);
 993       bitmap_clear (bb_info->out);
 994     }
 995 }
 996
 997
 998 /* Confluence function that processes infinite loops.  This might be a
 999    noreturn function that throws.  And even if it isn't, getting the
1000    unwind info right helps debugging.  */
1001 static void
1002 df_lr_confluence_0 (basic_block bb)
1003 {
1004   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
1005   if (bb != EXIT_BLOCK_PTR)
1006     bitmap_copy (op1, df->hardware_regs_used);
1007 }
1008
1009
1010 /* Confluence function that ignores fake edges.  */
1011
1012 static void
1013 df_lr_confluence_n (edge e)
1014 {
1015   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1016   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
1017
1018   /* Call-clobbered registers die across exception and call edges.  */
1019   /* ??? Abnormal call edges ignored for the moment, as this gets
1020      confused by sibling call edges, which crashes reg-stack.  */
1021   if (e->flags & EDGE_EH)
1022     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1023   else
1024     bitmap_ior_into (op1, op2);
1025
1026   bitmap_ior_into (op1, df->hardware_regs_used);
1027 }
1028
1029
1030 /* Transfer function.  */
1031
1032 static bool
1033 df_lr_transfer_function (int bb_index)
1034 {
1035   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1036   bitmap in = bb_info->in;
1037   bitmap out = bb_info->out;
1038   bitmap use = bb_info->use;
1039   bitmap def = bb_info->def;
1040
1041   return bitmap_ior_and_compl (in, use, out, def);
1042 }
1043
1044
1045 /* Run the fast dce as a side effect of building LR.  */
1046
1047 static void
1048 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1049 {
1050   if (df->changeable_flags & DF_LR_RUN_DCE)
1051     {
1052       run_fast_df_dce ();
1053       if (df_lr->problem_data && df_lr->solutions_dirty)
1054         {
1055           /* If we are here, then it is because we are both verifying
1056           the solution and the dce changed the function.  In that case
1057           the verification info built will be wrong.  So we leave the
1058           dirty flag true so that the verifier will skip the checking
1059           part and just clean up.*/
1060           df_lr->solutions_dirty = true;
1061         }
1062       else
1063         df_lr->solutions_dirty = false;
1064     }
1065   else
1066     df_lr->solutions_dirty = false;
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   struct 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           df_insn_create_insn_record (insn);
1476         }
1477
1478       DF_INSN_LUID (insn) = luid;
1479       if (!INSN_P (insn))
1480         continue;
1481
1482       luid++;
1483       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1484         {
1485           struct 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       struct 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 (struct df_ref *src, struct df_ref *dst)
1906 {
1907   struct df_link *head = DF_REF_CHAIN (src);
1908   struct df_link *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 (struct df_ref *ref, struct 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 (struct 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 (struct 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       struct df_ref **def_rec;
1991       struct 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                                 struct df_ref **use_rec,
2063                                 enum df_ref_flags top_flag)
2064 {
2065   bitmap_iterator bi;
2066   unsigned int def_index;
2067
2068   while (*use_rec)
2069     {
2070       struct 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                       struct 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   struct df_ref **def_rec;
2115
2116   bitmap_copy (cpy, bb_info->in);
2117   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2118
2119   /* Since we are going forwards, process the artificial uses first
2120      then the artificial defs second.  */
2121
2122 #ifdef EH_USES
2123   /* Create the chains for the artificial uses from the EH_USES at the
2124      beginning of the block.  */
2125
2126   /* Artificials are only hard regs.  */
2127   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2128     df_chain_create_bb_process_use (cpy,
2129                                     df_get_artificial_uses (bb->index),
2130                                     DF_REF_AT_TOP);
2131 #endif
2132
2133   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2134     {
2135       struct df_ref *def = *def_rec;
2136       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2137         {
2138           unsigned int dregno = DF_REF_REGNO (def);
2139           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2140             bitmap_clear_range (cpy,
2141                                 DF_DEFS_BEGIN (dregno),
2142                                 DF_DEFS_COUNT (dregno));
2143           bitmap_set_bit (cpy, DF_REF_ID (def));
2144         }
2145     }
2146
2147   /* Process the regular instructions next.  */
2148   FOR_BB_INSNS (bb, insn)
2149     {
2150       struct df_ref **def_rec;
2151       unsigned int uid = INSN_UID (insn);
2152
2153       if (!INSN_P (insn))
2154         continue;
2155
2156       /* Now scan the uses and link them up with the defs that remain
2157          in the cpy vector.  */
2158
2159       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2160
2161       if (df->changeable_flags & DF_EQ_NOTES)
2162         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2163
2164
2165       /* Since we are going forwards, process the defs second.  This
2166          pass only changes the bits in cpy.  */
2167       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2168         {
2169           struct df_ref *def = *def_rec;
2170           unsigned int dregno = DF_REF_REGNO (def);
2171           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2172               || (dregno >= FIRST_PSEUDO_REGISTER))
2173             {
2174               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2175                 bitmap_clear_range (cpy,
2176                                     DF_DEFS_BEGIN (dregno),
2177                                     DF_DEFS_COUNT (dregno));
2178               if (!(DF_REF_FLAGS (def)
2179                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2180                 bitmap_set_bit (cpy, DF_REF_ID (def));
2181             }
2182         }
2183     }
2184
2185   /* Create the chains for the artificial uses of the hard registers
2186      at the end of the block.  */
2187   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2188     df_chain_create_bb_process_use (cpy,
2189                                     df_get_artificial_uses (bb->index),
2190                                     0);
2191
2192   BITMAP_FREE (cpy);
2193 }
2194
2195 /* Create def-use chains from reaching use bitmaps for basic blocks
2196    in BLOCKS.  */
2197
2198 static void
2199 df_chain_finalize (bitmap all_blocks)
2200 {
2201   unsigned int bb_index;
2202   bitmap_iterator bi;
2203
2204   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2205     {
2206       df_chain_create_bb (bb_index);
2207     }
2208 }
2209
2210
2211 /* Free all storage associated with the problem.  */
2212
2213 static void
2214 df_chain_free (void)
2215 {
2216   free_alloc_pool (df_chain->block_pool);
2217   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2218   free (df_chain);
2219 }
2220
2221
2222 /* Debugging info.  */
2223
2224 static void
2225 df_chain_top_dump (basic_block bb, FILE *file)
2226 {
2227   if (df_chain_problem_p (DF_DU_CHAIN))
2228     {
2229       rtx insn;
2230       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2231       if (*def_rec)
2232         {
2233
2234           fprintf (file, ";;  DU chains for artificial defs\n");
2235           while (*def_rec)
2236             {
2237               struct df_ref *def = *def_rec;
2238               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2239               df_chain_dump (DF_REF_CHAIN (def), file);
2240               fprintf (file, "\n");
2241               def_rec++;
2242             }
2243         }
2244
2245       FOR_BB_INSNS (bb, insn)
2246         {
2247           unsigned int uid = INSN_UID (insn);
2248           if (INSN_P (insn))
2249             {
2250               def_rec = DF_INSN_UID_DEFS (uid);
2251               if (*def_rec)
2252                 {
2253                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2254                            DF_INSN_LUID (insn), uid);
2255
2256                   while (*def_rec)
2257                     {
2258                       struct df_ref *def = *def_rec;
2259                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2260                       if (def->flags & DF_REF_READ_WRITE)
2261                         fprintf (file, "read/write ");
2262                       df_chain_dump (DF_REF_CHAIN (def), file);
2263                       fprintf (file, "\n");
2264                       def_rec++;
2265                     }
2266                 }
2267             }
2268         }
2269     }
2270 }
2271
2272
2273 static void
2274 df_chain_bottom_dump (basic_block bb, FILE *file)
2275 {
2276   if (df_chain_problem_p (DF_UD_CHAIN))
2277     {
2278       rtx insn;
2279       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2280
2281       if (*use_rec)
2282         {
2283           fprintf (file, ";;  UD chains for artificial uses\n");
2284           while (*use_rec)
2285             {
2286               struct df_ref *use = *use_rec;
2287               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2288               df_chain_dump (DF_REF_CHAIN (use), file);
2289               fprintf (file, "\n");
2290               use_rec++;
2291             }
2292         }
2293
2294       FOR_BB_INSNS (bb, insn)
2295         {
2296           unsigned int uid = INSN_UID (insn);
2297           if (INSN_P (insn))
2298             {
2299               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2300               use_rec = DF_INSN_UID_USES (uid);
2301               if (*use_rec || *eq_use_rec)
2302                 {
2303                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2304                            DF_INSN_LUID (insn), uid);
2305
2306                   while (*use_rec)
2307                     {
2308                       struct df_ref *use = *use_rec;
2309                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2310                       if (use->flags & DF_REF_READ_WRITE)
2311                         fprintf (file, "read/write ");
2312                       df_chain_dump (DF_REF_CHAIN (use), file);
2313                       fprintf (file, "\n");
2314                       use_rec++;
2315                     }
2316                   while (*eq_use_rec)
2317                     {
2318                       struct df_ref *use = *eq_use_rec;
2319                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2320                       df_chain_dump (DF_REF_CHAIN (use), file);
2321                       fprintf (file, "\n");
2322                       eq_use_rec++;
2323                     }
2324                 }
2325             }
2326         }
2327     }
2328 }
2329
2330
2331 static struct df_problem problem_CHAIN =
2332 {
2333   DF_CHAIN,                   /* Problem id.  */
2334   DF_NONE,                    /* Direction.  */
2335   df_chain_alloc,             /* Allocate the problem specific data.  */
2336   df_chain_reset,             /* Reset global information.  */
2337   NULL,                       /* Free basic block info.  */
2338   NULL,                       /* Local compute function.  */
2339   NULL,                       /* Init the solution specific data.  */
2340   NULL,                       /* Iterative solver.  */
2341   NULL,                       /* Confluence operator 0.  */
2342   NULL,                       /* Confluence operator n.  */
2343   NULL,                       /* Transfer function.  */
2344   df_chain_finalize,          /* Finalize function.  */
2345   df_chain_free,              /* Free all of the problem information.  */
2346   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2347   NULL,                       /* Debugging.  */
2348   df_chain_top_dump,          /* Debugging start block.  */
2349   df_chain_bottom_dump,       /* Debugging end block.  */
2350   NULL,                       /* Incremental solution verify start.  */
2351   NULL,                       /* Incremental solution verify end.  */
2352   &problem_RD,                /* Dependent problem.  */
2353   TV_DF_CHAIN,                /* Timing variable.  */
2354   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2355 };
2356
2357
2358 /* Create a new DATAFLOW instance and add it to an existing instance
2359    of DF.  The returned structure is what is used to get at the
2360    solution.  */
2361
2362 void
2363 df_chain_add_problem (enum df_chain_flags chain_flags)
2364 {
2365   df_add_problem (&problem_CHAIN);
2366   df_chain->local_flags = (unsigned int)chain_flags;
2367   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2368 }
2369
2370 #undef df_chain_problem_p
2371
2372 \f
2373 /*----------------------------------------------------------------------------
2374    This pass computes REG_DEAD and REG_UNUSED notes.
2375    ----------------------------------------------------------------------------*/
2376
2377 static void
2378 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2379 {
2380   df_note->optional_p = true;
2381 }
2382
2383 #ifdef REG_DEAD_DEBUGGING
2384 static void
2385 df_print_note (const char *prefix, rtx insn, rtx note)
2386 {
2387   if (dump_file)
2388     {
2389       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2390       print_rtl (dump_file, note);
2391       fprintf (dump_file, "\n");
2392     }
2393 }
2394 #endif
2395
2396
2397 /* After reg-stack, the x86 floating point stack regs are difficult to
2398    analyze because of all of the pushes, pops and rotations.  Thus, we
2399    just leave the notes alone. */
2400
2401 #ifdef STACK_REGS
2402 static inline bool
2403 df_ignore_stack_reg (int regno)
2404 {
2405   return regstack_completed
2406     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2407 }
2408 #else
2409 static inline bool
2410 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2411 {
2412   return false;
2413 }
2414 #endif
2415
2416
2417 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
2418    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
2419
2420 static void
2421 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
2422 {
2423   rtx *pprev = &REG_NOTES (insn);
2424   rtx link = *pprev;
2425   rtx dead = NULL;
2426   rtx unused = NULL;
2427
2428   while (link)
2429     {
2430       switch (REG_NOTE_KIND (link))
2431         {
2432         case REG_DEAD:
2433           /* After reg-stack, we need to ignore any unused notes
2434              for the stack registers.  */
2435           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2436             {
2437               pprev = &XEXP (link, 1);
2438               link = *pprev;
2439             }
2440           else
2441             {
2442               rtx next = XEXP (link, 1);
2443 #ifdef REG_DEAD_DEBUGGING
2444               df_print_note ("deleting: ", insn, link);
2445 #endif
2446               XEXP (link, 1) = dead;
2447               dead = link;
2448               *pprev = link = next;
2449             }
2450           break;
2451
2452         case REG_UNUSED:
2453           /* After reg-stack, we need to ignore any unused notes
2454              for the stack registers.  */
2455           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2456             {
2457               pprev = &XEXP (link, 1);
2458               link = *pprev;
2459             }
2460           else
2461             {
2462               rtx next = XEXP (link, 1);
2463 #ifdef REG_DEAD_DEBUGGING
2464               df_print_note ("deleting: ", insn, link);
2465 #endif
2466               XEXP (link, 1) = unused;
2467               unused = link;
2468               *pprev = link = next;
2469             }
2470           break;
2471
2472         default:
2473           pprev = &XEXP (link, 1);
2474           link = *pprev;
2475           break;
2476         }
2477     }
2478
2479   *old_dead_notes = dead;
2480   *old_unused_notes = unused;
2481 }
2482
2483
2484 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
2485    list, otherwise create a new one.  */
2486
2487 static inline rtx
2488 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
2489 {
2490   rtx this = old;
2491   rtx prev = NULL;
2492
2493   while (this)
2494     if (XEXP (this, 0) == reg)
2495       {
2496         if (prev)
2497           XEXP (prev, 1) = XEXP (this, 1);
2498         else
2499           old = XEXP (this, 1);
2500         XEXP (this, 1) = REG_NOTES (insn);
2501         REG_NOTES (insn) = this;
2502         return old;
2503       }
2504     else
2505       {
2506         prev = this;
2507         this = XEXP (this, 1);
2508       }
2509
2510   /* Did not find the note.  */
2511   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
2512   return old;
2513 }
2514
2515 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2516    arguments.  Return true if the register value described by MWS's
2517    mw_reg is known to be completely unused, and if mw_reg can therefore
2518    be used in a REG_UNUSED note.  */
2519
2520 static bool
2521 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2522                           bitmap live, bitmap artificial_uses)
2523 {
2524   unsigned int r;
2525
2526   /* If MWS describes a partial reference, create REG_UNUSED notes for
2527      individual hard registers.  */
2528   if (mws->flags & DF_REF_PARTIAL)
2529     return false;
2530
2531   /* Likewise if some part of the register is used.  */
2532   for (r = mws->start_regno; r <= mws->end_regno; r++)
2533     if (bitmap_bit_p (live, r)
2534         || bitmap_bit_p (artificial_uses, r))
2535       return false;
2536
2537   gcc_assert (REG_P (mws->mw_reg));
2538   return true;
2539 }
2540
2541 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2542    based on the bits in LIVE.  Do not generate notes for registers in
2543    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2544    not generated if the reg is both read and written by the
2545    instruction.
2546 */
2547
2548 static rtx
2549 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2550                             bitmap live, bitmap do_not_gen,
2551                             bitmap artificial_uses)
2552 {
2553   unsigned int r;
2554
2555 #ifdef REG_DEAD_DEBUGGING
2556   if (dump_file)
2557     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2558              mws->start_regno, mws->end_regno);
2559 #endif
2560
2561   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2562     {
2563       unsigned int regno = mws->start_regno;
2564       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
2565
2566 #ifdef REG_DEAD_DEBUGGING
2567       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2568 #endif
2569       bitmap_set_bit (do_not_gen, regno);
2570       /* Only do this if the value is totally dead.  */
2571     }
2572   else
2573     for (r = mws->start_regno; r <= mws->end_regno; r++)
2574       {
2575         if (!bitmap_bit_p (live, r)
2576             && !bitmap_bit_p (artificial_uses, r))
2577           {
2578             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
2579 #ifdef REG_DEAD_DEBUGGING
2580             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2581 #endif
2582           }
2583         bitmap_set_bit (do_not_gen, r);
2584       }
2585   return old;
2586 }
2587
2588
2589 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2590    arguments.  Return true if the register value described by MWS's
2591    mw_reg is known to be completely dead, and if mw_reg can therefore
2592    be used in a REG_DEAD note.  */
2593
2594 static bool
2595 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2596                         bitmap live, bitmap artificial_uses,
2597                         bitmap do_not_gen)
2598 {
2599   unsigned int r;
2600
2601   /* If MWS describes a partial reference, create REG_DEAD notes for
2602      individual hard registers.  */
2603   if (mws->flags & DF_REF_PARTIAL)
2604     return false;
2605
2606   /* Likewise if some part of the register is not dead.  */
2607   for (r = mws->start_regno; r <= mws->end_regno; r++)
2608     if (bitmap_bit_p (live, r)
2609         || bitmap_bit_p (artificial_uses, r)
2610         || bitmap_bit_p (do_not_gen, r))
2611       return false;
2612
2613   gcc_assert (REG_P (mws->mw_reg));
2614   return true;
2615 }
2616
2617 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2618    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2619    from being set if the instruction both reads and writes the
2620    register.  */
2621
2622 static rtx
2623 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2624                           bitmap live, bitmap do_not_gen,
2625                           bitmap artificial_uses)
2626 {
2627   unsigned int r;
2628
2629 #ifdef REG_DEAD_DEBUGGING
2630   if (dump_file)
2631     {
2632       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
2633                mws->start_regno, mws->end_regno);
2634       df_print_regset (dump_file, do_not_gen);
2635       fprintf (dump_file, "  live =");
2636       df_print_regset (dump_file, live);
2637       fprintf (dump_file, "  artificial uses =");
2638       df_print_regset (dump_file, artificial_uses);
2639     }
2640 #endif
2641
2642   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
2643     {
2644       /* Add a dead note for the entire multi word register.  */
2645       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
2646 #ifdef REG_DEAD_DEBUGGING
2647       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2648 #endif
2649     }
2650   else
2651     {
2652       for (r = mws->start_regno; r <= mws->end_regno; r++)
2653         if (!bitmap_bit_p (live, r)
2654             && !bitmap_bit_p (artificial_uses, r)
2655             && !bitmap_bit_p (do_not_gen, r))
2656           {
2657             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
2658 #ifdef REG_DEAD_DEBUGGING
2659             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2660 #endif
2661           }
2662     }
2663   return old;
2664 }
2665
2666
2667 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
2668    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
2669
2670 static rtx
2671 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
2672                        bitmap live, bitmap artificial_uses)
2673 {
2674   unsigned int dregno = DF_REF_REGNO (def);
2675
2676 #ifdef REG_DEAD_DEBUGGING
2677   if (dump_file)
2678     {
2679       fprintf (dump_file, "  regular looking at def ");
2680       df_ref_debug (def, dump_file);
2681     }
2682 #endif
2683
2684   if (!(bitmap_bit_p (live, dregno)
2685         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
2686         || bitmap_bit_p (artificial_uses, dregno)
2687         || df_ignore_stack_reg (dregno)))
2688     {
2689       rtx reg = (DF_REF_LOC (def))
2690                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
2691       old = df_set_note (REG_UNUSED, insn, old, reg);
2692 #ifdef REG_DEAD_DEBUGGING
2693       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
2694 #endif
2695     }
2696
2697   return old;
2698 }
2699
2700
2701 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
2702    info: lifetime, bb, and number of defs and uses for basic block
2703    BB.  The three bitvectors are scratch regs used here.  */
2704
2705 static void
2706 df_note_bb_compute (unsigned int bb_index,
2707                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
2708 {
2709   basic_block bb = BASIC_BLOCK (bb_index);
2710   rtx insn;
2711   struct df_ref **def_rec;
2712   struct df_ref **use_rec;
2713
2714   bitmap_copy (live, df_get_live_out (bb));
2715   bitmap_clear (artificial_uses);
2716
2717 #ifdef REG_DEAD_DEBUGGING
2718   if (dump_file)
2719     {
2720       fprintf (dump_file, "live at bottom ");
2721       df_print_regset (dump_file, live);
2722     }
2723 #endif
2724
2725   /* Process the artificial defs and uses at the bottom of the block
2726      to begin processing.  */
2727   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2728     {
2729       struct df_ref *def = *def_rec;
2730 #ifdef REG_DEAD_DEBUGGING
2731       if (dump_file)
2732         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
2733 #endif
2734
2735       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2736         bitmap_clear_bit (live, DF_REF_REGNO (def));
2737     }
2738
2739   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2740     {
2741       struct df_ref *use = *use_rec;
2742       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2743         {
2744           unsigned int regno = DF_REF_REGNO (use);
2745           bitmap_set_bit (live, regno);
2746
2747           /* Notes are not generated for any of the artificial registers
2748              at the bottom of the block.  */
2749           bitmap_set_bit (artificial_uses, regno);
2750         }
2751     }
2752
2753 #ifdef REG_DEAD_DEBUGGING
2754   if (dump_file)
2755     {
2756       fprintf (dump_file, "live before artificials out ");
2757       df_print_regset (dump_file, live);
2758     }
2759 #endif
2760
2761   FOR_BB_INSNS_REVERSE (bb, insn)
2762     {
2763       unsigned int uid = INSN_UID (insn);
2764       struct df_mw_hardreg **mws_rec;
2765       rtx old_dead_notes;
2766       rtx old_unused_notes;
2767
2768       if (!INSN_P (insn))
2769         continue;
2770
2771       bitmap_clear (do_not_gen);
2772       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
2773
2774       /* Process the defs.  */
2775       if (CALL_P (insn))
2776         {
2777 #ifdef REG_DEAD_DEBUGGING
2778           if (dump_file)
2779             {
2780               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
2781               df_print_regset (dump_file, live);
2782             }
2783 #endif
2784           /* We only care about real sets for calls.  Clobbers cannot
2785              be depended on to really die.  */
2786           mws_rec = DF_INSN_UID_MWS (uid);
2787           while (*mws_rec)
2788             {
2789               struct df_mw_hardreg *mws = *mws_rec;
2790               if ((mws->type == DF_REF_REG_DEF)
2791                   && !df_ignore_stack_reg (mws->start_regno))
2792                 old_unused_notes
2793                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2794                                                 mws, live, do_not_gen,
2795                                                 artificial_uses);
2796               mws_rec++;
2797             }
2798
2799           /* All of the defs except the return value are some sort of
2800              clobber.  This code is for the return.  */
2801           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2802             {
2803               struct df_ref *def = *def_rec;
2804               unsigned int dregno = DF_REF_REGNO (def);
2805               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2806                 {
2807                   old_unused_notes
2808                     = df_create_unused_note (insn, old_unused_notes,
2809                                              def, live, artificial_uses);
2810                   bitmap_set_bit (do_not_gen, dregno);
2811                 }
2812
2813               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2814                 bitmap_clear_bit (live, dregno);
2815             }
2816         }
2817       else
2818         {
2819           /* Regular insn.  */
2820           mws_rec = DF_INSN_UID_MWS (uid);
2821           while (*mws_rec)
2822             {
2823               struct df_mw_hardreg *mws = *mws_rec;
2824               if (mws->type == DF_REF_REG_DEF)
2825                 old_unused_notes
2826                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2827                                                 mws, live, do_not_gen,
2828                                                 artificial_uses);
2829               mws_rec++;
2830             }
2831
2832           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2833             {
2834               struct df_ref *def = *def_rec;
2835               unsigned int dregno = DF_REF_REGNO (def);
2836               old_unused_notes
2837                 = df_create_unused_note (insn, old_unused_notes,
2838                                          def, live, artificial_uses);
2839
2840               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2841                 bitmap_set_bit (do_not_gen, dregno);
2842
2843               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2844                 bitmap_clear_bit (live, dregno);
2845             }
2846         }
2847
2848       /* Process the uses.  */
2849       mws_rec = DF_INSN_UID_MWS (uid);
2850       while (*mws_rec)
2851         {
2852           struct df_mw_hardreg *mws = *mws_rec;
2853           if ((mws->type != DF_REF_REG_DEF)
2854               && !df_ignore_stack_reg (mws->start_regno))
2855             old_dead_notes
2856               = df_set_dead_notes_for_mw (insn, old_dead_notes,
2857                                           mws, live, do_not_gen,
2858                                           artificial_uses);
2859           mws_rec++;
2860         }
2861
2862       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2863         {
2864           struct df_ref *use = *use_rec;
2865           unsigned int uregno = DF_REF_REGNO (use);
2866
2867 #ifdef REG_DEAD_DEBUGGING
2868           if (dump_file)
2869             {
2870               fprintf (dump_file, "  regular looking at use ");
2871               df_ref_debug (use, dump_file);
2872             }
2873 #endif
2874           if (!bitmap_bit_p (live, uregno))
2875             {
2876               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
2877                    && (!bitmap_bit_p (do_not_gen, uregno))
2878                    && (!bitmap_bit_p (artificial_uses, uregno))
2879                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
2880                    && (!df_ignore_stack_reg (uregno)))
2881                 {
2882                   rtx reg = (DF_REF_LOC (use))
2883                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
2884                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
2885
2886 #ifdef REG_DEAD_DEBUGGING
2887                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
2888 #endif
2889                 }
2890               /* This register is now live.  */
2891               bitmap_set_bit (live, uregno);
2892             }
2893         }
2894
2895       while (old_unused_notes)
2896         {
2897           rtx next = XEXP (old_unused_notes, 1);
2898           free_EXPR_LIST_node (old_unused_notes);
2899           old_unused_notes = next;
2900         }
2901       while (old_dead_notes)
2902         {
2903           rtx next = XEXP (old_dead_notes, 1);
2904           free_EXPR_LIST_node (old_dead_notes);
2905           old_dead_notes = next;
2906         }
2907     }
2908 }
2909
2910
2911 /* Compute register info: lifetime, bb, and number of defs and uses.  */
2912 static void
2913 df_note_compute (bitmap all_blocks)
2914 {
2915   unsigned int bb_index;
2916   bitmap_iterator bi;
2917   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
2918   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
2919   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
2920
2921 #ifdef REG_DEAD_DEBUGGING
2922   if (dump_file)
2923     print_rtl_with_bb (dump_file, get_insns());
2924 #endif
2925
2926   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2927   {
2928     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
2929   }
2930
2931   BITMAP_FREE (live);
2932   BITMAP_FREE (do_not_gen);
2933   BITMAP_FREE (artificial_uses);
2934 }
2935
2936
2937 /* Free all storage associated with the problem.  */
2938
2939 static void
2940 df_note_free (void)
2941 {
2942   free (df_note);
2943 }
2944
2945
2946 /* All of the information associated every instance of the problem.  */
2947
2948 static struct df_problem problem_NOTE =
2949 {
2950   DF_NOTE,                    /* Problem id.  */
2951   DF_NONE,                    /* Direction.  */
2952   df_note_alloc,              /* Allocate the problem specific data.  */
2953   NULL,                       /* Reset global information.  */
2954   NULL,                       /* Free basic block info.  */
2955   df_note_compute,            /* Local compute function.  */
2956   NULL,                       /* Init the solution specific data.  */
2957   NULL,                       /* Iterative solver.  */
2958   NULL,                       /* Confluence operator 0.  */
2959   NULL,                       /* Confluence operator n.  */
2960   NULL,                       /* Transfer function.  */
2961   NULL,                       /* Finalize function.  */
2962   df_note_free,               /* Free all of the problem information.  */
2963   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
2964   NULL,                       /* Debugging.  */
2965   NULL,                       /* Debugging start block.  */
2966   NULL,                       /* Debugging end block.  */
2967   NULL,                       /* Incremental solution verify start.  */
2968   NULL,                       /* Incremental solution verify end.  */
2969   &problem_LR,                /* Dependent problem.  */
2970   TV_DF_NOTE,                 /* Timing variable.  */
2971   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2972 };
2973
2974
2975 /* Create a new DATAFLOW instance and add it to an existing instance
2976    of DF.  The returned structure is what is used to get at the
2977    solution.  */
2978
2979 void
2980 df_note_add_problem (void)
2981 {
2982   df_add_problem (&problem_NOTE);
2983 }
2984
2985
2986
2987 \f
2988 /*----------------------------------------------------------------------------
2989    Functions for simulating the effects of single insns.
2990
2991    You can either simulate in the forwards direction, starting from
2992    the top of a block or the backwards direction from the end of the
2993    block.  The main difference is that if you go forwards, the uses
2994    are examined first then the defs, and if you go backwards, the defs
2995    are examined first then the uses.
2996
2997    If you start at the top of the block, use one of DF_LIVE_IN or
2998    DF_LR_IN.  If you start at the bottom of the block use one of
2999    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3000    THEY WILL BE DESTROYED.
3001
3002 ----------------------------------------------------------------------------*/
3003
3004
3005 /* Find the set of DEFs for INSN.  */
3006
3007 void
3008 df_simulate_find_defs (rtx insn, bitmap defs)
3009 {
3010   struct df_ref **def_rec;
3011   unsigned int uid = INSN_UID (insn);
3012
3013   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3014     {
3015       struct df_ref *def = *def_rec;
3016       /* If the def is to only part of the reg, it does
3017          not kill the other defs that reach here.  */
3018       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3019         bitmap_set_bit (defs, DF_REF_REGNO (def));
3020     }
3021 }
3022
3023
3024 /* Simulate the effects of the defs of INSN on LIVE.  */
3025
3026 void
3027 df_simulate_defs (rtx insn, bitmap live)
3028 {
3029   struct df_ref **def_rec;
3030   unsigned int uid = INSN_UID (insn);
3031
3032   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3033     {
3034       struct df_ref *def = *def_rec;
3035       unsigned int dregno = DF_REF_REGNO (def);
3036
3037       /* If the def is to only part of the reg, it does
3038          not kill the other defs that reach here.  */
3039       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3040         bitmap_clear_bit (live, dregno);
3041     }
3042 }
3043
3044
3045 /* Simulate the effects of the uses of INSN on LIVE.  */
3046
3047 void
3048 df_simulate_uses (rtx insn, bitmap live)
3049 {
3050   struct df_ref **use_rec;
3051   unsigned int uid = INSN_UID (insn);
3052
3053   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3054     {
3055       struct df_ref *use = *use_rec;
3056       /* Add use to set of uses in this BB.  */
3057       bitmap_set_bit (live, DF_REF_REGNO (use));
3058     }
3059 }
3060
3061
3062 /* Add back the always live regs in BB to LIVE.  */
3063
3064 static inline void
3065 df_simulate_fixup_sets (basic_block bb, bitmap live)
3066 {
3067   /* These regs are considered always live so if they end up dying
3068      because of some def, we need to bring the back again.  */
3069   if (bb_has_eh_pred (bb))
3070     bitmap_ior_into (live, df->eh_block_artificial_uses);
3071   else
3072     bitmap_ior_into (live, df->regular_block_artificial_uses);
3073 }
3074
3075
3076 /* Apply the artificial uses and defs at the top of BB in a forwards
3077    direction.  */
3078
3079 void
3080 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3081 {
3082   struct df_ref **def_rec;
3083   struct df_ref **use_rec;
3084   int bb_index = bb->index;
3085
3086   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3087     {
3088       struct df_ref *use = *use_rec;
3089       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3090         bitmap_set_bit (live, DF_REF_REGNO (use));
3091     }
3092
3093   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3094     {
3095       struct df_ref *def = *def_rec;
3096       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3097         bitmap_clear_bit (live, DF_REF_REGNO (def));
3098     }
3099 }
3100
3101
3102 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3103
3104 void
3105 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3106 {
3107   if (! INSN_P (insn))
3108     return;
3109
3110   df_simulate_uses (insn, live);
3111   df_simulate_defs (insn, live);
3112   df_simulate_fixup_sets (bb, live);
3113 }
3114
3115
3116 /* Apply the artificial uses and defs at the end of BB in a backwards
3117    direction.  */
3118
3119 void
3120 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3121 {
3122   struct df_ref **def_rec;
3123   struct df_ref **use_rec;
3124   int bb_index = bb->index;
3125
3126   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3127     {
3128       struct df_ref *def = *def_rec;
3129       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3130         bitmap_clear_bit (live, DF_REF_REGNO (def));
3131     }
3132
3133   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3134     {
3135       struct df_ref *use = *use_rec;
3136       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3137         bitmap_set_bit (live, DF_REF_REGNO (use));
3138     }
3139 }
3140
3141
3142 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3143
3144 void
3145 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3146 {
3147   if (! INSN_P (insn))
3148     return;
3149
3150   df_simulate_defs (insn, live);
3151   df_simulate_uses (insn, live);
3152   df_simulate_fixup_sets (bb, live);
3153 }
3154
3155