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       BITMAP_FREE (bb_info->kill);
 249       BITMAP_FREE (bb_info->sparse_kill);
 250       BITMAP_FREE (bb_info->gen);
 251       BITMAP_FREE (bb_info->in);
 252       BITMAP_FREE (bb_info->out);
 253       pool_free (df_rd->block_pool, bb_info);
 254     }
 255 }
 256
 257
 258 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
 259    not touched unless the block is new.  */
 260
 261 static void
 262 df_rd_alloc (bitmap all_blocks)
 263 {
 264   unsigned int bb_index;
 265   bitmap_iterator bi;
 266   struct df_rd_problem_data *problem_data;
 267
 268   if (!df_rd->block_pool)
 269     df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
 270                                            sizeof (struct df_rd_bb_info), 50);
 271
 272   if (df_rd->problem_data)
 273     {
 274       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 275       bitmap_clear (problem_data->sparse_invalidated_by_call);
 276       bitmap_clear (problem_data->dense_invalidated_by_call);
 277     }
 278   else
 279     {
 280       problem_data = XNEW (struct df_rd_problem_data);
 281       df_rd->problem_data = problem_data;
 282
 283       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
 284       problem_data->sparse_invalidated_by_call
 285         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 286       problem_data->dense_invalidated_by_call
 287         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 288     }
 289
 290   df_grow_bb_info (df_rd);
 291
 292   /* Because of the clustering of all use sites for the same pseudo,
 293      we have to process all of the blocks before doing the
 294      analysis.  */
 295
 296   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 297     {
 298       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 299       if (bb_info)
 300         {
 301           bitmap_clear (bb_info->kill);
 302           bitmap_clear (bb_info->sparse_kill);
 303           bitmap_clear (bb_info->gen);
 304         }
 305       else
 306         {
 307           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
 308           df_rd_set_bb_info (bb_index, bb_info);
 309           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 310           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 311           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 312           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 313           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 314         }
 315     }
 316   df_rd->optional_p = true;
 317 }
 318
 319
 320 /* Process a list of DEFs for df_rd_bb_local_compute.  */
 321
 322 static void
 323 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
 324                                     struct df_ref **def_rec,
 325                                     enum df_ref_flags top_flag)
 326 {
 327   while (*def_rec)
 328     {
 329       struct df_ref *def = *def_rec;
 330       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
 331         {
 332           unsigned int regno = DF_REF_REGNO (def);
 333           unsigned int begin = DF_DEFS_BEGIN (regno);
 334           unsigned int n_defs = DF_DEFS_COUNT (regno);
 335
 336           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
 337               || (regno >= FIRST_PSEUDO_REGISTER))
 338             {
 339               /* Only the last def(s) for a regno in the block has any
 340                  effect.  */
 341               if (!bitmap_bit_p (seen_in_block, regno))
 342                 {
 343                   /* The first def for regno in insn gets to knock out the
 344                      defs from other instructions.  */
 345                   if ((!bitmap_bit_p (seen_in_insn, regno))
 346                       /* If the def is to only part of the reg, it does
 347                          not kill the other defs that reach here.  */
 348                       && (!(DF_REF_FLAGS (def) &
 349                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
 350                     {
 351                       if (n_defs > DF_SPARSE_THRESHOLD)
 352                         {
 353                           bitmap_set_bit (bb_info->sparse_kill, regno);
 354                           bitmap_clear_range(bb_info->gen, begin, n_defs);
 355                         }
 356                       else
 357                         {
 358                           bitmap_set_range (bb_info->kill, begin, n_defs);
 359                           bitmap_clear_range (bb_info->gen, begin, n_defs);
 360                         }
 361                     }
 362
 363                   bitmap_set_bit (seen_in_insn, regno);
 364                   /* All defs for regno in the instruction may be put into
 365                      the gen set.  */
 366                   if (!(DF_REF_FLAGS (def)
 367                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
 368                     bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
 369                 }
 370             }
 371         }
 372       def_rec++;
 373     }
 374 }
 375
 376 /* Compute local reaching def info for basic block BB.  */
 377
 378 static void
 379 df_rd_bb_local_compute (unsigned int bb_index)
 380 {
 381   basic_block bb = BASIC_BLOCK (bb_index);
 382   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 383   rtx insn;
 384
 385   bitmap_clear (seen_in_block);
 386   bitmap_clear (seen_in_insn);
 387
 388   /* Artificials are only hard regs.  */
 389   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 390     df_rd_bb_local_compute_process_def (bb_info,
 391                                         df_get_artificial_defs (bb_index),
 392                                         0);
 393
 394   FOR_BB_INSNS_REVERSE (bb, insn)
 395     {
 396       unsigned int uid = INSN_UID (insn);
 397
 398       if (!INSN_P (insn))
 399         continue;
 400
 401       df_rd_bb_local_compute_process_def (bb_info,
 402                                           DF_INSN_UID_DEFS (uid), 0);
 403
 404       /* This complex dance with the two bitmaps is required because
 405          instructions can assign twice to the same pseudo.  This
 406          generally happens with calls that will have one def for the
 407          result and another def for the clobber.  If only one vector
 408          is used and the clobber goes first, the result will be
 409          lost.  */
 410       bitmap_ior_into (seen_in_block, seen_in_insn);
 411       bitmap_clear (seen_in_insn);
 412     }
 413
 414   /* Process the artificial defs at the top of the block last since we
 415      are going backwards through the block and these are logically at
 416      the start.  */
 417   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 418     df_rd_bb_local_compute_process_def (bb_info,
 419                                         df_get_artificial_defs (bb_index),
 420                                         DF_REF_AT_TOP);
 421 }
 422
 423
 424 /* Compute local reaching def info for each basic block within BLOCKS.  */
 425
 426 static void
 427 df_rd_local_compute (bitmap all_blocks)
 428 {
 429   unsigned int bb_index;
 430   bitmap_iterator bi;
 431   unsigned int regno;
 432   struct df_rd_problem_data *problem_data
 433     = (struct df_rd_problem_data *) df_rd->problem_data;
 434   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 435   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 436
 437   df_set_seen ();
 438
 439   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
 440
 441   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 442     {
 443       df_rd_bb_local_compute (bb_index);
 444     }
 445
 446   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
 447   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
 448     {
 449       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
 450         bitmap_set_bit (sparse_invalidated, regno);
 451       else
 452         bitmap_set_range (dense_invalidated,
 453                           DF_DEFS_BEGIN (regno),
 454                           DF_DEFS_COUNT (regno));
 455     }
 456   df_unset_seen ();
 457 }
 458
 459
 460 /* Initialize the solution bit vectors for problem.  */
 461
 462 static void
 463 df_rd_init_solution (bitmap all_blocks)
 464 {
 465   unsigned int bb_index;
 466   bitmap_iterator bi;
 467
 468   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 469     {
 470       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 471
 472       bitmap_copy (bb_info->out, bb_info->gen);
 473       bitmap_clear (bb_info->in);
 474     }
 475 }
 476
 477 /* In of target gets or of out of source.  */
 478
 479 static void
 480 df_rd_confluence_n (edge e)
 481 {
 482   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
 483   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
 484
 485   if (e->flags & EDGE_EH)
 486     {
 487       struct df_rd_problem_data *problem_data
 488         = (struct df_rd_problem_data *) df_rd->problem_data;
 489       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 490       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 491       bitmap_iterator bi;
 492       unsigned int regno;
 493       bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
 494
 495       bitmap_copy (tmp, op2);
 496       bitmap_and_compl_into (tmp, dense_invalidated);
 497
 498       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
 499         {
 500           bitmap_clear_range (tmp,
 501                               DF_DEFS_BEGIN (regno),
 502                               DF_DEFS_COUNT (regno));
 503         }
 504       bitmap_ior_into (op1, tmp);
 505       BITMAP_FREE (tmp);
 506     }
 507   else
 508     bitmap_ior_into (op1, op2);
 509 }
 510
 511
 512 /* Transfer function.  */
 513
 514 static bool
 515 df_rd_transfer_function (int bb_index)
 516 {
 517   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 518   unsigned int regno;
 519   bitmap_iterator bi;
 520   bitmap in = bb_info->in;
 521   bitmap out = bb_info->out;
 522   bitmap gen = bb_info->gen;
 523   bitmap kill = bb_info->kill;
 524   bitmap sparse_kill = bb_info->sparse_kill;
 525
 526   if (bitmap_empty_p (sparse_kill))
 527     return  bitmap_ior_and_compl (out, gen, in, kill);
 528   else
 529     {
 530       struct df_rd_problem_data *problem_data;
 531       bool changed = false;
 532       bitmap tmp;
 533
 534       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
 535          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
 536       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 537       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 538
 539       bitmap_copy (tmp, in);
 540       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
 541         {
 542           bitmap_clear_range (tmp,
 543                               DF_DEFS_BEGIN (regno),
 544                               DF_DEFS_COUNT (regno));
 545         }
 546       bitmap_and_compl_into (tmp, kill);
 547       bitmap_ior_into (tmp, gen);
 548       changed = !bitmap_equal_p (tmp, out);
 549       if (changed)
 550         {
 551           BITMAP_FREE (out);
 552           bb_info->out = tmp;
 553         }
 554       else
 555           BITMAP_FREE (tmp);
 556       return changed;
 557     }
 558 }
 559
 560
 561 /* Free all storage associated with the problem.  */
 562
 563 static void
 564 df_rd_free (void)
 565 {
 566   unsigned int i;
 567   struct df_rd_problem_data *problem_data
 568     = (struct df_rd_problem_data *) df_rd->problem_data;
 569
 570   if (problem_data)
 571     {
 572       for (i = 0; i < df_rd->block_info_size; i++)
 573         {
 574           struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
 575           if (bb_info)
 576             {
 577               BITMAP_FREE (bb_info->kill);
 578               BITMAP_FREE (bb_info->sparse_kill);
 579               BITMAP_FREE (bb_info->gen);
 580               BITMAP_FREE (bb_info->in);
 581               BITMAP_FREE (bb_info->out);
 582             }
 583         }
 584
 585       free_alloc_pool (df_rd->block_pool);
 586       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
 587       BITMAP_FREE (problem_data->dense_invalidated_by_call);
 588       bitmap_obstack_release (&problem_data->rd_bitmaps);
 589
 590       df_rd->block_info_size = 0;
 591       free (df_rd->block_info);
 592       free (df_rd->problem_data);
 593     }
 594   free (df_rd);
 595 }
 596
 597
 598 /* Debugging info.  */
 599
 600 static void
 601 df_rd_start_dump (FILE *file)
 602 {
 603   struct df_rd_problem_data *problem_data
 604     = (struct df_rd_problem_data *) df_rd->problem_data;
 605   unsigned int m = DF_REG_SIZE(df);
 606   unsigned int regno;
 607
 608   if (!df_rd->block_info)
 609     return;
 610
 611   fprintf (file, ";; Reaching defs:\n\n");
 612
 613   fprintf (file, "  sparse invalidated \t");
 614   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
 615   fprintf (file, "  dense invalidated \t");
 616   dump_bitmap (file, problem_data->dense_invalidated_by_call);
 617
 618   for (regno = 0; regno < m; regno++)
 619     if (DF_DEFS_COUNT (regno))
 620       fprintf (file, "%d[%d,%d] ", regno,
 621                DF_DEFS_BEGIN (regno),
 622                DF_DEFS_COUNT (regno));
 623   fprintf (file, "\n");
 624
 625 }
 626
 627
 628 /* Debugging info at top of bb.  */
 629
 630 static void
 631 df_rd_top_dump (basic_block bb, FILE *file)
 632 {
 633   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 634   if (!bb_info || !bb_info->in)
 635     return;
 636
 637   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
 638   dump_bitmap (file, bb_info->in);
 639   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
 640   dump_bitmap (file, bb_info->gen);
 641   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
 642   dump_bitmap (file, bb_info->kill);
 643 }
 644
 645
 646 /* Debugging info at top of bb.  */
 647
 648 static void
 649 df_rd_bottom_dump (basic_block bb, FILE *file)
 650 {
 651   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 652   if (!bb_info || !bb_info->out)
 653     return;
 654
 655   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
 656   dump_bitmap (file, bb_info->out);
 657 }
 658
 659 /* All of the information associated with every instance of the problem.  */
 660
 661 static struct df_problem problem_RD =
 662 {
 663   DF_RD,                      /* Problem id.  */
 664   DF_FORWARD,                 /* Direction.  */
 665   df_rd_alloc,                /* Allocate the problem specific data.  */
 666   NULL,                       /* Reset global information.  */
 667   df_rd_free_bb_info,         /* Free basic block info.  */
 668   df_rd_local_compute,        /* Local compute function.  */
 669   df_rd_init_solution,        /* Init the solution specific data.  */
 670   df_worklist_dataflow,       /* Worklist solver.  */
 671   NULL,                       /* Confluence operator 0.  */
 672   df_rd_confluence_n,         /* Confluence operator n.  */
 673   df_rd_transfer_function,    /* Transfer function.  */
 674   NULL,                       /* Finalize function.  */
 675   df_rd_free,                 /* Free all of the problem information.  */
 676   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
 677   df_rd_start_dump,           /* Debugging.  */
 678   df_rd_top_dump,             /* Debugging start block.  */
 679   df_rd_bottom_dump,          /* Debugging end block.  */
 680   NULL,                       /* Incremental solution verify start.  */
 681   NULL,                       /* Incremental solution verify end.  */
 682   NULL,                       /* Dependent problem.  */
 683   TV_DF_RD,                   /* Timing variable.  */
 684   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 685 };
 686
 687
 688
 689 /* Create a new DATAFLOW instance and add it to an existing instance
 690    of DF.  The returned structure is what is used to get at the
 691    solution.  */
 692
 693 void
 694 df_rd_add_problem (void)
 695 {
 696   df_add_problem (&problem_RD);
 697 }
 698
 699
 700 \f
 701 /*----------------------------------------------------------------------------
 702    LIVE REGISTERS
 703
 704    Find the locations in the function where any use of a pseudo can
 705    reach in the backwards direction.  In and out bitvectors are built
 706    for each basic block.  The regnum is used to index into these sets.
 707    See df.h for details.
 708    ----------------------------------------------------------------------------*/
 709
 710 /* Private data used to verify the solution for this problem.  */
 711 struct df_lr_problem_data
 712 {
 713   bitmap *in;
 714   bitmap *out;
 715 };
 716
 717
 718 /* Set basic block info.  */
 719
 720 static void
 721 df_lr_set_bb_info (unsigned int index,
 722                    struct df_lr_bb_info *bb_info)
 723 {
 724   gcc_assert (df_lr);
 725   gcc_assert (index < df_lr->block_info_size);
 726   df_lr->block_info[index] = bb_info;
 727 }
 728
 729
 730 /* Free basic block info.  */
 731
 732 static void
 733 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 734                     void *vbb_info)
 735 {
 736   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
 737   if (bb_info)
 738     {
 739       BITMAP_FREE (bb_info->use);
 740       BITMAP_FREE (bb_info->def);
 741       BITMAP_FREE (bb_info->in);
 742       BITMAP_FREE (bb_info->out);
 743       pool_free (df_lr->block_pool, bb_info);
 744     }
 745 }
 746
 747
 748 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
 749    not touched unless the block is new.  */
 750
 751 static void
 752 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 753 {
 754   unsigned int bb_index;
 755   bitmap_iterator bi;
 756
 757   if (!df_lr->block_pool)
 758     df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
 759                                            sizeof (struct df_lr_bb_info), 50);
 760
 761   df_grow_bb_info (df_lr);
 762
 763   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 764     {
 765       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 766       if (bb_info)
 767         {
 768           bitmap_clear (bb_info->def);
 769           bitmap_clear (bb_info->use);
 770         }
 771       else
 772         {
 773           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
 774           df_lr_set_bb_info (bb_index, bb_info);
 775           bb_info->use = BITMAP_ALLOC (NULL);
 776           bb_info->def = BITMAP_ALLOC (NULL);
 777           bb_info->in = BITMAP_ALLOC (NULL);
 778           bb_info->out = BITMAP_ALLOC (NULL);
 779         }
 780     }
 781
 782   df_lr->optional_p = false;
 783 }
 784
 785
 786 /* Reset the global solution for recalculation.  */
 787
 788 static void
 789 df_lr_reset (bitmap all_blocks)
 790 {
 791   unsigned int bb_index;
 792   bitmap_iterator bi;
 793
 794   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 795     {
 796       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 797       gcc_assert (bb_info);
 798       bitmap_clear (bb_info->in);
 799       bitmap_clear (bb_info->out);
 800     }
 801 }
 802
 803
 804 /* Compute local live register info for basic block BB.  */
 805
 806 static void
 807 df_lr_bb_local_compute (unsigned int bb_index)
 808 {
 809   basic_block bb = BASIC_BLOCK (bb_index);
 810   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 811   rtx insn;
 812   struct df_ref **def_rec;
 813   struct df_ref **use_rec;
 814
 815   /* Process the registers set in an exception handler.  */
 816   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 817     {
 818       struct df_ref *def = *def_rec;
 819       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 820         {
 821           unsigned int dregno = DF_REF_REGNO (def);
 822           bitmap_set_bit (bb_info->def, dregno);
 823           bitmap_clear_bit (bb_info->use, dregno);
 824         }
 825     }
 826
 827   /* Process the hardware registers that are always live.  */
 828   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 829     {
 830       struct df_ref *use = *use_rec;
 831       /* Add use to set of uses in this BB.  */
 832       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 833         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 834     }
 835
 836   FOR_BB_INSNS_REVERSE (bb, insn)
 837     {
 838       unsigned int uid = INSN_UID (insn);
 839
 840       if (!INSN_P (insn))
 841         continue;
 842
 843       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 844         {
 845           struct df_ref *def = *def_rec;
 846           /* If the def is to only part of the reg, it does
 847              not kill the other defs that reach here.  */
 848           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 849             {
 850               unsigned int dregno = DF_REF_REGNO (def);
 851               bitmap_set_bit (bb_info->def, dregno);
 852               bitmap_clear_bit (bb_info->use, dregno);
 853             }
 854         }
 855
 856       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 857         {
 858           struct df_ref *use = *use_rec;
 859           /* Add use to set of uses in this BB.  */
 860           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 861         }
 862     }
 863
 864   /* Process the registers set in an exception handler or the hard
 865      frame pointer if this block is the target of a non local
 866      goto.  */
 867   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 868     {
 869       struct df_ref *def = *def_rec;
 870       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 871         {
 872           unsigned int dregno = DF_REF_REGNO (def);
 873           bitmap_set_bit (bb_info->def, dregno);
 874           bitmap_clear_bit (bb_info->use, dregno);
 875         }
 876     }
 877
 878 #ifdef EH_USES
 879   /* Process the uses that are live into an exception handler.  */
 880   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 881     {
 882       struct df_ref *use = *use_rec;
 883       /* Add use to set of uses in this BB.  */
 884       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 885         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 886     }
 887 #endif
 888
 889   /* If the df_live problem is not defined, such as at -O0 and -O1, we
 890      still need to keep the luids up to date.  This is normally done
 891      in the df_live problem since this problem has a forwards
 892      scan.  */
 893   if (!df_live)
 894     df_recompute_luids (bb);
 895 }
 896
 897
 898 /* Compute local live register info for each basic block within BLOCKS.  */
 899
 900 static void
 901 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
 902 {
 903   unsigned int bb_index;
 904   bitmap_iterator bi;
 905
 906   bitmap_clear (df->hardware_regs_used);
 907
 908   /* The all-important stack pointer must always be live.  */
 909   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
 910
 911   /* Before reload, there are a few registers that must be forced
 912      live everywhere -- which might not already be the case for
 913      blocks within infinite loops.  */
 914   if (!reload_completed)
 915     {
 916       /* Any reference to any pseudo before reload is a potential
 917          reference of the frame pointer.  */
 918       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
 919
 920 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
 921       /* Pseudos with argument area equivalences may require
 922          reloading via the argument pointer.  */
 923       if (fixed_regs[ARG_POINTER_REGNUM])
 924         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
 925 #endif
 926
 927       /* Any constant, or pseudo with constant equivalences, may
 928          require reloading from memory using the pic register.  */
 929       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
 930           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
 931         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
 932     }
 933
 934   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 935     {
 936       if (bb_index == EXIT_BLOCK)
 937         {
 938           /* The exit block is special for this problem and its bits are
 939              computed from thin air.  */
 940           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
 941           bitmap_copy (bb_info->use, df->exit_block_uses);
 942         }
 943       else
 944         df_lr_bb_local_compute (bb_index);
 945     }
 946
 947   bitmap_clear (df_lr->out_of_date_transfer_functions);
 948 }
 949
 950
 951 /* Initialize the solution vectors.  */
 952
 953 static void
 954 df_lr_init (bitmap all_blocks)
 955 {
 956   unsigned int bb_index;
 957   bitmap_iterator bi;
 958
 959   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 960     {
 961       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 962       bitmap_copy (bb_info->in, bb_info->use);
 963       bitmap_clear (bb_info->out);
 964     }
 965 }
 966
 967
 968 /* Confluence function that processes infinite loops.  This might be a
 969    noreturn function that throws.  And even if it isn't, getting the
 970    unwind info right helps debugging.  */
 971 static void
 972 df_lr_confluence_0 (basic_block bb)
 973 {
 974   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
 975   if (bb != EXIT_BLOCK_PTR)
 976     bitmap_copy (op1, df->hardware_regs_used);
 977 }
 978
 979
 980 /* Confluence function that ignores fake edges.  */
 981
 982 static void
 983 df_lr_confluence_n (edge e)
 984 {
 985   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
 986   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
 987
 988   /* Call-clobbered registers die across exception and call edges.  */
 989   /* ??? Abnormal call edges ignored for the moment, as this gets
 990      confused by sibling call edges, which crashes reg-stack.  */
 991   if (e->flags & EDGE_EH)
 992     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
 993   else
 994     bitmap_ior_into (op1, op2);
 995
 996   bitmap_ior_into (op1, df->hardware_regs_used);
 997 }
 998
 999
1000 /* Transfer function.  */
1001
1002 static bool
1003 df_lr_transfer_function (int bb_index)
1004 {
1005   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1006   bitmap in = bb_info->in;
1007   bitmap out = bb_info->out;
1008   bitmap use = bb_info->use;
1009   bitmap def = bb_info->def;
1010
1011   return bitmap_ior_and_compl (in, use, out, def);
1012 }
1013
1014
1015 /* Run the fast dce as a side effect of building LR.  */
1016
1017 static void
1018 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1019 {
1020   if (df->changeable_flags & DF_LR_RUN_DCE)
1021     {
1022       run_fast_df_dce ();
1023       if (df_lr->problem_data && df_lr->solutions_dirty)
1024         {
1025           /* If we are here, then it is because we are both verifying
1026           the solution and the dce changed the function.  In that case
1027           the verification info built will be wrong.  So we leave the
1028           dirty flag true so that the verifier will skip the checking
1029           part and just clean up.*/
1030           df_lr->solutions_dirty = true;
1031         }
1032       else
1033         df_lr->solutions_dirty = false;
1034     }
1035   else
1036     df_lr->solutions_dirty = false;
1037 }
1038
1039
1040 /* Free all storage associated with the problem.  */
1041
1042 static void
1043 df_lr_free (void)
1044 {
1045   if (df_lr->block_info)
1046     {
1047       unsigned int i;
1048       for (i = 0; i < df_lr->block_info_size; i++)
1049         {
1050           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1051           if (bb_info)
1052             {
1053               BITMAP_FREE (bb_info->use);
1054               BITMAP_FREE (bb_info->def);
1055               BITMAP_FREE (bb_info->in);
1056               BITMAP_FREE (bb_info->out);
1057             }
1058         }
1059       free_alloc_pool (df_lr->block_pool);
1060
1061       df_lr->block_info_size = 0;
1062       free (df_lr->block_info);
1063     }
1064
1065   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1066   free (df_lr);
1067 }
1068
1069
1070 /* Debugging info at top of bb.  */
1071
1072 static void
1073 df_lr_top_dump (basic_block bb, FILE *file)
1074 {
1075   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1076   struct df_lr_problem_data *problem_data;
1077   if (!bb_info || !bb_info->in)
1078     return;
1079
1080   fprintf (file, ";; lr  in  \t");
1081   df_print_regset (file, bb_info->in);
1082   if (df_lr->problem_data)
1083     {
1084       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1085       fprintf (file, ";;  old in  \t");
1086       df_print_regset (file, problem_data->in[bb->index]);
1087     }
1088   fprintf (file, ";; lr  use \t");
1089   df_print_regset (file, bb_info->use);
1090   fprintf (file, ";; lr  def \t");
1091   df_print_regset (file, bb_info->def);
1092 }
1093
1094
1095 /* Debugging info at bottom of bb.  */
1096
1097 static void
1098 df_lr_bottom_dump (basic_block bb, FILE *file)
1099 {
1100   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1101   struct df_lr_problem_data *problem_data;
1102   if (!bb_info || !bb_info->out)
1103     return;
1104
1105   fprintf (file, ";; lr  out \t");
1106   df_print_regset (file, bb_info->out);
1107   if (df_lr->problem_data)
1108     {
1109       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1110       fprintf (file, ";;  old out  \t");
1111       df_print_regset (file, problem_data->out[bb->index]);
1112     }
1113 }
1114
1115
1116 /* Build the datastructure to verify that the solution to the dataflow
1117    equations is not dirty.  */
1118
1119 static void
1120 df_lr_verify_solution_start (void)
1121 {
1122   basic_block bb;
1123   struct df_lr_problem_data *problem_data;
1124   if (df_lr->solutions_dirty)
1125     {
1126       df_lr->problem_data = NULL;
1127       return;
1128     }
1129
1130   /* Set it true so that the solution is recomputed.  */
1131   df_lr->solutions_dirty = true;
1132
1133   problem_data = XNEW (struct df_lr_problem_data);
1134   df_lr->problem_data = problem_data;
1135   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1136   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1137
1138   FOR_ALL_BB (bb)
1139     {
1140       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1141       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1142       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1143       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1144     }
1145 }
1146
1147
1148 /* Compare the saved datastructure and the new solution to the dataflow
1149    equations.  */
1150
1151 static void
1152 df_lr_verify_solution_end (void)
1153 {
1154   struct df_lr_problem_data *problem_data;
1155   basic_block bb;
1156
1157   if (df_lr->problem_data == NULL)
1158     return;
1159
1160   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1161
1162   if (df_lr->solutions_dirty)
1163     /* Do not check if the solution is still dirty.  See the comment
1164        in df_lr_local_finalize for details.  */
1165     df_lr->solutions_dirty = false;
1166   else
1167     FOR_ALL_BB (bb)
1168       {
1169         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1170             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1171           {
1172             /*df_dump (stderr);*/
1173             gcc_unreachable ();
1174           }
1175       }
1176
1177   /* Cannot delete them immediately because you may want to dump them
1178      if the comparison fails.  */
1179   FOR_ALL_BB (bb)
1180     {
1181       BITMAP_FREE (problem_data->in[bb->index]);
1182       BITMAP_FREE (problem_data->out[bb->index]);
1183     }
1184
1185   free (problem_data->in);
1186   free (problem_data->out);
1187   free (problem_data);
1188   df_lr->problem_data = NULL;
1189 }
1190
1191
1192 /* All of the information associated with every instance of the problem.  */
1193
1194 static struct df_problem problem_LR =
1195 {
1196   DF_LR,                      /* Problem id.  */
1197   DF_BACKWARD,                /* Direction.  */
1198   df_lr_alloc,                /* Allocate the problem specific data.  */
1199   df_lr_reset,                /* Reset global information.  */
1200   df_lr_free_bb_info,         /* Free basic block info.  */
1201   df_lr_local_compute,        /* Local compute function.  */
1202   df_lr_init,                 /* Init the solution specific data.  */
1203   df_worklist_dataflow,       /* Worklist solver.  */
1204   df_lr_confluence_0,         /* Confluence operator 0.  */
1205   df_lr_confluence_n,         /* Confluence operator n.  */
1206   df_lr_transfer_function,    /* Transfer function.  */
1207   df_lr_local_finalize,       /* Finalize function.  */
1208   df_lr_free,                 /* Free all of the problem information.  */
1209   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1210   NULL,                       /* Debugging.  */
1211   df_lr_top_dump,             /* Debugging start block.  */
1212   df_lr_bottom_dump,          /* Debugging end block.  */
1213   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1214   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1215   NULL,                       /* Dependent problem.  */
1216   TV_DF_LR,                   /* Timing variable.  */
1217   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1218 };
1219
1220
1221 /* Create a new DATAFLOW instance and add it to an existing instance
1222    of DF.  The returned structure is what is used to get at the
1223    solution.  */
1224
1225 void
1226 df_lr_add_problem (void)
1227 {
1228   df_add_problem (&problem_LR);
1229   /* These will be initialized when df_scan_blocks processes each
1230      block.  */
1231   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1232 }
1233
1234
1235 /* Verify that all of the lr related info is consistent and
1236    correct.  */
1237
1238 void
1239 df_lr_verify_transfer_functions (void)
1240 {
1241   basic_block bb;
1242   bitmap saved_def;
1243   bitmap saved_use;
1244   bitmap saved_adef;
1245   bitmap saved_ause;
1246   bitmap all_blocks;
1247
1248   if (!df)
1249     return;
1250
1251   saved_def = BITMAP_ALLOC (NULL);
1252   saved_use = BITMAP_ALLOC (NULL);
1253   saved_adef = BITMAP_ALLOC (NULL);
1254   saved_ause = BITMAP_ALLOC (NULL);
1255   all_blocks = BITMAP_ALLOC (NULL);
1256
1257   FOR_ALL_BB (bb)
1258     {
1259       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1260       bitmap_set_bit (all_blocks, bb->index);
1261
1262       if (bb_info)
1263         {
1264           /* Make a copy of the transfer functions and then compute
1265              new ones to see if the transfer functions have
1266              changed.  */
1267           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1268                              bb->index))
1269             {
1270               bitmap_copy (saved_def, bb_info->def);
1271               bitmap_copy (saved_use, bb_info->use);
1272               bitmap_clear (bb_info->def);
1273               bitmap_clear (bb_info->use);
1274
1275               df_lr_bb_local_compute (bb->index);
1276               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1277               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1278             }
1279         }
1280       else
1281         {
1282           /* If we do not have basic block info, the block must be in
1283              the list of dirty blocks or else some one has added a
1284              block behind our backs. */
1285           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1286                                     bb->index));
1287         }
1288       /* Make sure no one created a block without following
1289          procedures.  */
1290       gcc_assert (df_scan_get_bb_info (bb->index));
1291     }
1292
1293   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1294   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1295                                          all_blocks));
1296
1297   BITMAP_FREE (saved_def);
1298   BITMAP_FREE (saved_use);
1299   BITMAP_FREE (saved_adef);
1300   BITMAP_FREE (saved_ause);
1301   BITMAP_FREE (all_blocks);
1302 }
1303
1304
1305 \f
1306 /*----------------------------------------------------------------------------
1307    COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1308
1309    First find the set of uses for registers that are reachable from
1310    the entry block without passing thru a definition.  In and out
1311    bitvectors are built for each basic block.  The regnum is used to
1312    index into these sets.  See df.h for details.
1313
1314    Then the in and out sets here are the anded results of the in and
1315    out sets from the lr and ur
1316    problems.
1317 ----------------------------------------------------------------------------*/
1318
1319 /* Private data used to verify the solution for this problem.  */
1320 struct df_live_problem_data
1321 {
1322   bitmap *in;
1323   bitmap *out;
1324 };
1325
1326
1327 /* Set basic block info.  */
1328
1329 static void
1330 df_live_set_bb_info (unsigned int index,
1331                    struct df_live_bb_info *bb_info)
1332 {
1333   gcc_assert (df_live);
1334   gcc_assert (index < df_live->block_info_size);
1335   df_live->block_info[index] = bb_info;
1336 }
1337
1338
1339 /* Free basic block info.  */
1340
1341 static void
1342 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1343                     void *vbb_info)
1344 {
1345   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1346   if (bb_info)
1347     {
1348       BITMAP_FREE (bb_info->gen);
1349       BITMAP_FREE (bb_info->kill);
1350       BITMAP_FREE (bb_info->in);
1351       BITMAP_FREE (bb_info->out);
1352       pool_free (df_live->block_pool, bb_info);
1353     }
1354 }
1355
1356
1357 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1358    not touched unless the block is new.  */
1359
1360 static void
1361 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1362 {
1363   unsigned int bb_index;
1364   bitmap_iterator bi;
1365
1366   if (!df_live->block_pool)
1367     df_live->block_pool = create_alloc_pool ("df_live_block pool",
1368                                            sizeof (struct df_live_bb_info), 100);
1369
1370   df_grow_bb_info (df_live);
1371
1372   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1373     {
1374       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1375       if (bb_info)
1376         {
1377           bitmap_clear (bb_info->kill);
1378           bitmap_clear (bb_info->gen);
1379         }
1380       else
1381         {
1382           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1383           df_live_set_bb_info (bb_index, bb_info);
1384           bb_info->kill = BITMAP_ALLOC (NULL);
1385           bb_info->gen = BITMAP_ALLOC (NULL);
1386           bb_info->in = BITMAP_ALLOC (NULL);
1387           bb_info->out = BITMAP_ALLOC (NULL);
1388         }
1389     }
1390   df_live->optional_p = (optimize <= 1);
1391 }
1392
1393
1394 /* Reset the global solution for recalculation.  */
1395
1396 static void
1397 df_live_reset (bitmap all_blocks)
1398 {
1399   unsigned int bb_index;
1400   bitmap_iterator bi;
1401
1402   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1403     {
1404       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1405       gcc_assert (bb_info);
1406       bitmap_clear (bb_info->in);
1407       bitmap_clear (bb_info->out);
1408     }
1409 }
1410
1411
1412 /* Compute local uninitialized register info for basic block BB.  */
1413
1414 static void
1415 df_live_bb_local_compute (unsigned int bb_index)
1416 {
1417   basic_block bb = BASIC_BLOCK (bb_index);
1418   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1419   rtx insn;
1420   struct df_ref **def_rec;
1421   int luid = 0;
1422
1423   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1424     {
1425       struct df_ref *def = *def_rec;
1426       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1427         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1428     }
1429
1430   FOR_BB_INSNS (bb, insn)
1431     {
1432       unsigned int uid = INSN_UID (insn);
1433       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1434
1435       /* Inserting labels does not always trigger the incremental
1436          rescanning.  */
1437       if (!insn_info)
1438         {
1439           gcc_assert (!INSN_P (insn));
1440           df_insn_create_insn_record (insn);
1441         }
1442
1443       DF_INSN_LUID (insn) = luid;
1444       if (!INSN_P (insn))
1445         continue;
1446
1447       luid++;
1448       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1449         {
1450           struct df_ref *def = *def_rec;
1451           unsigned int regno = DF_REF_REGNO (def);
1452
1453           if (DF_REF_FLAGS_IS_SET (def,
1454                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1455             /* All partial or conditional def
1456                seen are included in the gen set. */
1457             bitmap_set_bit (bb_info->gen, regno);
1458           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1459             /* Only must clobbers for the entire reg destroy the
1460                value.  */
1461             bitmap_set_bit (bb_info->kill, regno);
1462           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1463             bitmap_set_bit (bb_info->gen, regno);
1464         }
1465     }
1466
1467   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1468     {
1469       struct df_ref *def = *def_rec;
1470       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1471         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1472     }
1473 }
1474
1475
1476 /* Compute local uninitialized register info.  */
1477
1478 static void
1479 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1480 {
1481   unsigned int bb_index;
1482   bitmap_iterator bi;
1483
1484   df_grow_insn_info ();
1485
1486   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1487                             0, bb_index, bi)
1488     {
1489       df_live_bb_local_compute (bb_index);
1490     }
1491
1492   bitmap_clear (df_live->out_of_date_transfer_functions);
1493 }
1494
1495
1496 /* Initialize the solution vectors.  */
1497
1498 static void
1499 df_live_init (bitmap all_blocks)
1500 {
1501   unsigned int bb_index;
1502   bitmap_iterator bi;
1503
1504   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1505     {
1506       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1507
1508       bitmap_copy (bb_info->out, bb_info->gen);
1509       bitmap_clear (bb_info->in);
1510     }
1511 }
1512
1513 /* Confluence function that ignores fake edges.  */
1514
1515 static void
1516 df_live_confluence_n (edge e)
1517 {
1518   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1519   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1520
1521   if (e->flags & EDGE_FAKE)
1522     return;
1523
1524   bitmap_ior_into (op1, op2);
1525 }
1526
1527
1528 /* Transfer function.  */
1529
1530 static bool
1531 df_live_transfer_function (int bb_index)
1532 {
1533   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1534   bitmap in = bb_info->in;
1535   bitmap out = bb_info->out;
1536   bitmap gen = bb_info->gen;
1537   bitmap kill = bb_info->kill;
1538
1539   return bitmap_ior_and_compl (out, gen, in, kill);
1540 }
1541
1542
1543 /* And the LR and UR info to produce the LIVE info.  */
1544
1545 static void
1546 df_live_local_finalize (bitmap all_blocks)
1547 {
1548
1549   if (df_live->solutions_dirty)
1550     {
1551       bitmap_iterator bi;
1552       unsigned int bb_index;
1553
1554       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1555         {
1556           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1557           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1558
1559           /* No register may reach a location where it is not used.  Thus
1560              we trim the rr result to the places where it is used.  */
1561           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1562           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1563         }
1564
1565       df_live->solutions_dirty = false;
1566     }
1567 }
1568
1569
1570 /* Free all storage associated with the problem.  */
1571
1572 static void
1573 df_live_free (void)
1574 {
1575   if (df_live->block_info)
1576     {
1577       unsigned int i;
1578
1579       for (i = 0; i < df_live->block_info_size; i++)
1580         {
1581           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1582           if (bb_info)
1583             {
1584               BITMAP_FREE (bb_info->gen);
1585               BITMAP_FREE (bb_info->kill);
1586               BITMAP_FREE (bb_info->in);
1587               BITMAP_FREE (bb_info->out);
1588             }
1589         }
1590
1591       free_alloc_pool (df_live->block_pool);
1592       df_live->block_info_size = 0;
1593       free (df_live->block_info);
1594     }
1595   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1596   free (df_live);
1597 }
1598
1599
1600 /* Debugging info at top of bb.  */
1601
1602 static void
1603 df_live_top_dump (basic_block bb, FILE *file)
1604 {
1605   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1606   struct df_live_problem_data *problem_data;
1607
1608   if (!bb_info || !bb_info->in)
1609     return;
1610
1611   fprintf (file, ";; live  in  \t");
1612   df_print_regset (file, bb_info->in);
1613   if (df_live->problem_data)
1614     {
1615       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1616       fprintf (file, ";;  old in  \t");
1617       df_print_regset (file, problem_data->in[bb->index]);
1618     }
1619   fprintf (file, ";; live  gen \t");
1620   df_print_regset (file, bb_info->gen);
1621   fprintf (file, ";; live  kill\t");
1622   df_print_regset (file, bb_info->kill);
1623 }
1624
1625
1626 /* Debugging info at bottom of bb.  */
1627
1628 static void
1629 df_live_bottom_dump (basic_block bb, FILE *file)
1630 {
1631   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1632   struct df_live_problem_data *problem_data;
1633
1634   if (!bb_info || !bb_info->out)
1635     return;
1636
1637   fprintf (file, ";; live  out \t");
1638   df_print_regset (file, bb_info->out);
1639   if (df_live->problem_data)
1640     {
1641       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1642       fprintf (file, ";;  old out  \t");
1643       df_print_regset (file, problem_data->out[bb->index]);
1644     }
1645 }
1646
1647
1648 /* Build the datastructure to verify that the solution to the dataflow
1649    equations is not dirty.  */
1650
1651 static void
1652 df_live_verify_solution_start (void)
1653 {
1654   basic_block bb;
1655   struct df_live_problem_data *problem_data;
1656   if (df_live->solutions_dirty)
1657     {
1658       df_live->problem_data = NULL;
1659       return;
1660     }
1661
1662   /* Set it true so that the solution is recomputed.  */
1663   df_live->solutions_dirty = true;
1664
1665   problem_data = XNEW (struct df_live_problem_data);
1666   df_live->problem_data = problem_data;
1667   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1668   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1669
1670   FOR_ALL_BB (bb)
1671     {
1672       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1673       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1674       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1675       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1676     }
1677 }
1678
1679
1680 /* Compare the saved datastructure and the new solution to the dataflow
1681    equations.  */
1682
1683 static void
1684 df_live_verify_solution_end (void)
1685 {
1686   struct df_live_problem_data *problem_data;
1687   basic_block bb;
1688
1689   if (df_live->problem_data == NULL)
1690     return;
1691
1692   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1693
1694   FOR_ALL_BB (bb)
1695     {
1696       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1697           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1698         {
1699           /*df_dump (stderr);*/
1700           gcc_unreachable ();
1701         }
1702     }
1703
1704   /* Cannot delete them immediately because you may want to dump them
1705      if the comparison fails.  */
1706   FOR_ALL_BB (bb)
1707     {
1708       BITMAP_FREE (problem_data->in[bb->index]);
1709       BITMAP_FREE (problem_data->out[bb->index]);
1710     }
1711
1712   free (problem_data->in);
1713   free (problem_data->out);
1714   free (problem_data);
1715   df_live->problem_data = NULL;
1716 }
1717
1718
1719 /* All of the information associated with every instance of the problem.  */
1720
1721 static struct df_problem problem_LIVE =
1722 {
1723   DF_LIVE,                      /* Problem id.  */
1724   DF_FORWARD,                   /* Direction.  */
1725   df_live_alloc,                /* Allocate the problem specific data.  */
1726   df_live_reset,                /* Reset global information.  */
1727   df_live_free_bb_info,         /* Free basic block info.  */
1728   df_live_local_compute,        /* Local compute function.  */
1729   df_live_init,                 /* Init the solution specific data.  */
1730   df_worklist_dataflow,         /* Worklist solver.  */
1731   NULL,                         /* Confluence operator 0.  */
1732   df_live_confluence_n,         /* Confluence operator n.  */
1733   df_live_transfer_function,    /* Transfer function.  */
1734   df_live_local_finalize,       /* Finalize function.  */
1735   df_live_free,                 /* Free all of the problem information.  */
1736   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1737   NULL,                         /* Debugging.  */
1738   df_live_top_dump,             /* Debugging start block.  */
1739   df_live_bottom_dump,          /* Debugging end block.  */
1740   df_live_verify_solution_start,/* Incremental solution verify start.  */
1741   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1742   &problem_LR,                  /* Dependent problem.  */
1743   TV_DF_LIVE,                   /* Timing variable.  */
1744   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1745 };
1746
1747
1748 /* Create a new DATAFLOW instance and add it to an existing instance
1749    of DF.  The returned structure is what is used to get at the
1750    solution.  */
1751
1752 void
1753 df_live_add_problem (void)
1754 {
1755   df_add_problem (&problem_LIVE);
1756   /* These will be initialized when df_scan_blocks processes each
1757      block.  */
1758   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1759 }
1760
1761
1762 /* Set all of the blocks as dirty.  This needs to be done if this
1763    problem is added after all of the insns have been scanned.  */
1764
1765 void
1766 df_live_set_all_dirty (void)
1767 {
1768   basic_block bb;
1769   FOR_ALL_BB (bb)
1770     bitmap_set_bit (df_live->out_of_date_transfer_functions,
1771                     bb->index);
1772 }
1773
1774
1775 /* Verify that all of the lr related info is consistent and
1776    correct.  */
1777
1778 void
1779 df_live_verify_transfer_functions (void)
1780 {
1781   basic_block bb;
1782   bitmap saved_gen;
1783   bitmap saved_kill;
1784   bitmap all_blocks;
1785
1786   if (!df)
1787     return;
1788
1789   saved_gen = BITMAP_ALLOC (NULL);
1790   saved_kill = BITMAP_ALLOC (NULL);
1791   all_blocks = BITMAP_ALLOC (NULL);
1792
1793   df_grow_insn_info ();
1794
1795   FOR_ALL_BB (bb)
1796     {
1797       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1798       bitmap_set_bit (all_blocks, bb->index);
1799
1800       if (bb_info)
1801         {
1802           /* Make a copy of the transfer functions and then compute
1803              new ones to see if the transfer functions have
1804              changed.  */
1805           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1806                              bb->index))
1807             {
1808               bitmap_copy (saved_gen, bb_info->gen);
1809               bitmap_copy (saved_kill, bb_info->kill);
1810               bitmap_clear (bb_info->gen);
1811               bitmap_clear (bb_info->kill);
1812
1813               df_live_bb_local_compute (bb->index);
1814               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1815               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1816             }
1817         }
1818       else
1819         {
1820           /* If we do not have basic block info, the block must be in
1821              the list of dirty blocks or else some one has added a
1822              block behind our backs. */
1823           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1824                                     bb->index));
1825         }
1826       /* Make sure no one created a block without following
1827          procedures.  */
1828       gcc_assert (df_scan_get_bb_info (bb->index));
1829     }
1830
1831   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1832   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1833                                          all_blocks));
1834   BITMAP_FREE (saved_gen);
1835   BITMAP_FREE (saved_kill);
1836   BITMAP_FREE (all_blocks);
1837 }
1838 \f
1839 /*----------------------------------------------------------------------------
1840    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1841
1842    Link either the defs to the uses and / or the uses to the defs.
1843
1844    These problems are set up like the other dataflow problems so that
1845    they nicely fit into the framework.  They are much simpler and only
1846    involve a single traversal of instructions and an examination of
1847    the reaching defs information (the dependent problem).
1848 ----------------------------------------------------------------------------*/
1849
1850 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1851
1852 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1853
1854 struct df_link *
1855 df_chain_create (struct df_ref *src, struct df_ref *dst)
1856 {
1857   struct df_link *head = DF_REF_CHAIN (src);
1858   struct df_link *link = pool_alloc (df_chain->block_pool);;
1859
1860   DF_REF_CHAIN (src) = link;
1861   link->next = head;
1862   link->ref = dst;
1863   return link;
1864 }
1865
1866
1867 /* Delete any du or ud chains that start at REF and point to
1868    TARGET.  */
1869 static void
1870 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1871 {
1872   struct df_link *chain = DF_REF_CHAIN (ref);
1873   struct df_link *prev = NULL;
1874
1875   while (chain)
1876     {
1877       if (chain->ref == target)
1878         {
1879           if (prev)
1880             prev->next = chain->next;
1881           else
1882             DF_REF_CHAIN (ref) = chain->next;
1883           pool_free (df_chain->block_pool, chain);
1884           return;
1885         }
1886       prev = chain;
1887       chain = chain->next;
1888     }
1889 }
1890
1891
1892 /* Delete a du or ud chain that leave or point to REF.  */
1893
1894 void
1895 df_chain_unlink (struct df_ref *ref)
1896 {
1897   struct df_link *chain = DF_REF_CHAIN (ref);
1898   while (chain)
1899     {
1900       struct df_link *next = chain->next;
1901       /* Delete the other side if it exists.  */
1902       df_chain_unlink_1 (chain->ref, ref);
1903       pool_free (df_chain->block_pool, chain);
1904       chain = next;
1905     }
1906   DF_REF_CHAIN (ref) = NULL;
1907 }
1908
1909
1910 /* Copy the du or ud chain starting at FROM_REF and attach it to
1911    TO_REF.  */
1912
1913 void
1914 df_chain_copy (struct df_ref *to_ref,
1915                struct df_link *from_ref)
1916 {
1917   while (from_ref)
1918     {
1919       df_chain_create (to_ref, from_ref->ref);
1920       from_ref = from_ref->next;
1921     }
1922 }
1923
1924
1925 /* Remove this problem from the stack of dataflow problems.  */
1926
1927 static void
1928 df_chain_remove_problem (void)
1929 {
1930   bitmap_iterator bi;
1931   unsigned int bb_index;
1932
1933   /* Wholesale destruction of the old chains.  */
1934   if (df_chain->block_pool)
1935     free_alloc_pool (df_chain->block_pool);
1936
1937   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1938     {
1939       rtx insn;
1940       struct df_ref **def_rec;
1941       struct df_ref **use_rec;
1942       basic_block bb = BASIC_BLOCK (bb_index);
1943
1944       if (df_chain_problem_p (DF_DU_CHAIN))
1945         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1946           DF_REF_CHAIN (*def_rec) = NULL;
1947       if (df_chain_problem_p (DF_UD_CHAIN))
1948         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1949           DF_REF_CHAIN (*use_rec) = NULL;
1950
1951       FOR_BB_INSNS (bb, insn)
1952         {
1953           unsigned int uid = INSN_UID (insn);
1954
1955           if (INSN_P (insn))
1956             {
1957               if (df_chain_problem_p (DF_DU_CHAIN))
1958                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1959                   DF_REF_CHAIN (*def_rec) = NULL;
1960               if (df_chain_problem_p (DF_UD_CHAIN))
1961                 {
1962                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1963                     DF_REF_CHAIN (*use_rec) = NULL;
1964                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1965                     DF_REF_CHAIN (*use_rec) = NULL;
1966                 }
1967             }
1968         }
1969     }
1970
1971   bitmap_clear (df_chain->out_of_date_transfer_functions);
1972   df_chain->block_pool = NULL;
1973 }
1974
1975
1976 /* Remove the chain problem completely.  */
1977
1978 static void
1979 df_chain_fully_remove_problem (void)
1980 {
1981   df_chain_remove_problem ();
1982   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1983   free (df_chain);
1984 }
1985
1986
1987 /* Create def-use or use-def chains.  */
1988
1989 static void
1990 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1991 {
1992   df_chain_remove_problem ();
1993   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
1994                                          sizeof (struct df_link), 50);
1995   df_chain->optional_p = true;
1996 }
1997
1998
1999 /* Reset all of the chains when the set of basic blocks changes.  */
2000
2001 static void
2002 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2003 {
2004   df_chain_remove_problem ();
2005 }
2006
2007
2008 /* Create the chains for a list of USEs.  */
2009
2010 static void
2011 df_chain_create_bb_process_use (bitmap local_rd,
2012                                 struct df_ref **use_rec,
2013                                 enum df_ref_flags top_flag)
2014 {
2015   bitmap_iterator bi;
2016   unsigned int def_index;
2017
2018   while (*use_rec)
2019     {
2020       struct df_ref *use = *use_rec;
2021       unsigned int uregno = DF_REF_REGNO (use);
2022       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2023           || (uregno >= FIRST_PSEUDO_REGISTER))
2024         {
2025           /* Do not want to go through this for an uninitialized var.  */
2026           int count = DF_DEFS_COUNT (uregno);
2027           if (count)
2028             {
2029               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2030                 {
2031                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2032                   unsigned int last_index = first_index + count - 1;
2033
2034                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2035                     {
2036                       struct df_ref *def;
2037                       if (def_index > last_index)
2038                         break;
2039
2040                       def = DF_DEFS_GET (def_index);
2041                       if (df_chain_problem_p (DF_DU_CHAIN))
2042                         df_chain_create (def, use);
2043                       if (df_chain_problem_p (DF_UD_CHAIN))
2044                         df_chain_create (use, def);
2045                     }
2046                 }
2047             }
2048         }
2049
2050       use_rec++;
2051     }
2052 }
2053
2054
2055 /* Create chains from reaching defs bitmaps for basic block BB.  */
2056
2057 static void
2058 df_chain_create_bb (unsigned int bb_index)
2059 {
2060   basic_block bb = BASIC_BLOCK (bb_index);
2061   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2062   rtx insn;
2063   bitmap cpy = BITMAP_ALLOC (NULL);
2064   struct df_ref **def_rec;
2065
2066   bitmap_copy (cpy, bb_info->in);
2067   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2068
2069   /* Since we are going forwards, process the artificial uses first
2070      then the artificial defs second.  */
2071
2072 #ifdef EH_USES
2073   /* Create the chains for the artificial uses from the EH_USES at the
2074      beginning of the block.  */
2075
2076   /* Artificials are only hard regs.  */
2077   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2078     df_chain_create_bb_process_use (cpy,
2079                                     df_get_artificial_uses (bb->index),
2080                                     DF_REF_AT_TOP);
2081 #endif
2082
2083   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2084     {
2085       struct df_ref *def = *def_rec;
2086       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2087         {
2088           unsigned int dregno = DF_REF_REGNO (def);
2089           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2090             bitmap_clear_range (cpy,
2091                                 DF_DEFS_BEGIN (dregno),
2092                                 DF_DEFS_COUNT (dregno));
2093           bitmap_set_bit (cpy, DF_REF_ID (def));
2094         }
2095     }
2096
2097   /* Process the regular instructions next.  */
2098   FOR_BB_INSNS (bb, insn)
2099     {
2100       struct df_ref **def_rec;
2101       unsigned int uid = INSN_UID (insn);
2102
2103       if (!INSN_P (insn))
2104         continue;
2105
2106       /* Now scan the uses and link them up with the defs that remain
2107          in the cpy vector.  */
2108
2109       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2110
2111       if (df->changeable_flags & DF_EQ_NOTES)
2112         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2113
2114
2115       /* Since we are going forwards, process the defs second.  This
2116          pass only changes the bits in cpy.  */
2117       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2118         {
2119           struct df_ref *def = *def_rec;
2120           unsigned int dregno = DF_REF_REGNO (def);
2121           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2122               || (dregno >= FIRST_PSEUDO_REGISTER))
2123             {
2124               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2125                 bitmap_clear_range (cpy,
2126                                     DF_DEFS_BEGIN (dregno),
2127                                     DF_DEFS_COUNT (dregno));
2128               if (!(DF_REF_FLAGS (def)
2129                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2130                 bitmap_set_bit (cpy, DF_REF_ID (def));
2131             }
2132         }
2133     }
2134
2135   /* Create the chains for the artificial uses of the hard registers
2136      at the end of the block.  */
2137   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2138     df_chain_create_bb_process_use (cpy,
2139                                     df_get_artificial_uses (bb->index),
2140                                     0);
2141
2142   BITMAP_FREE (cpy);
2143 }
2144
2145 /* Create def-use chains from reaching use bitmaps for basic blocks
2146    in BLOCKS.  */
2147
2148 static void
2149 df_chain_finalize (bitmap all_blocks)
2150 {
2151   unsigned int bb_index;
2152   bitmap_iterator bi;
2153
2154   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2155     {
2156       df_chain_create_bb (bb_index);
2157     }
2158 }
2159
2160
2161 /* Free all storage associated with the problem.  */
2162
2163 static void
2164 df_chain_free (void)
2165 {
2166   free_alloc_pool (df_chain->block_pool);
2167   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2168   free (df_chain);
2169 }
2170
2171
2172 /* Debugging info.  */
2173
2174 static void
2175 df_chain_top_dump (basic_block bb, FILE *file)
2176 {
2177   if (df_chain_problem_p (DF_DU_CHAIN))
2178     {
2179       rtx insn;
2180       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2181       if (*def_rec)
2182         {
2183
2184           fprintf (file, ";;  DU chains for artificial defs\n");
2185           while (*def_rec)
2186             {
2187               struct df_ref *def = *def_rec;
2188               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2189               df_chain_dump (DF_REF_CHAIN (def), file);
2190               fprintf (file, "\n");
2191               def_rec++;
2192             }
2193         }
2194
2195       FOR_BB_INSNS (bb, insn)
2196         {
2197           unsigned int uid = INSN_UID (insn);
2198           if (INSN_P (insn))
2199             {
2200               def_rec = DF_INSN_UID_DEFS (uid);
2201               if (*def_rec)
2202                 {
2203                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2204                            DF_INSN_LUID (insn), uid);
2205
2206                   while (*def_rec)
2207                     {
2208                       struct df_ref *def = *def_rec;
2209                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2210                       if (def->flags & DF_REF_READ_WRITE)
2211                         fprintf (file, "read/write ");
2212                       df_chain_dump (DF_REF_CHAIN (def), file);
2213                       fprintf (file, "\n");
2214                       def_rec++;
2215                     }
2216                 }
2217             }
2218         }
2219     }
2220 }
2221
2222
2223 static void
2224 df_chain_bottom_dump (basic_block bb, FILE *file)
2225 {
2226   if (df_chain_problem_p (DF_UD_CHAIN))
2227     {
2228       rtx insn;
2229       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2230
2231       if (*use_rec)
2232         {
2233           fprintf (file, ";;  UD chains for artificial uses\n");
2234           while (*use_rec)
2235             {
2236               struct df_ref *use = *use_rec;
2237               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2238               df_chain_dump (DF_REF_CHAIN (use), file);
2239               fprintf (file, "\n");
2240               use_rec++;
2241             }
2242         }
2243
2244       FOR_BB_INSNS (bb, insn)
2245         {
2246           unsigned int uid = INSN_UID (insn);
2247           if (INSN_P (insn))
2248             {
2249               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2250               use_rec = DF_INSN_UID_USES (uid);
2251               if (*use_rec || *eq_use_rec)
2252                 {
2253                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2254                            DF_INSN_LUID (insn), uid);
2255
2256                   while (*use_rec)
2257                     {
2258                       struct df_ref *use = *use_rec;
2259                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2260                       if (use->flags & DF_REF_READ_WRITE)
2261                         fprintf (file, "read/write ");
2262                       df_chain_dump (DF_REF_CHAIN (use), file);
2263                       fprintf (file, "\n");
2264                       use_rec++;
2265                     }
2266                   while (*eq_use_rec)
2267                     {
2268                       struct df_ref *use = *eq_use_rec;
2269                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2270                       df_chain_dump (DF_REF_CHAIN (use), file);
2271                       fprintf (file, "\n");
2272                       eq_use_rec++;
2273                     }
2274                 }
2275             }
2276         }
2277     }
2278 }
2279
2280
2281 static struct df_problem problem_CHAIN =
2282 {
2283   DF_CHAIN,                   /* Problem id.  */
2284   DF_NONE,                    /* Direction.  */
2285   df_chain_alloc,             /* Allocate the problem specific data.  */
2286   df_chain_reset,             /* Reset global information.  */
2287   NULL,                       /* Free basic block info.  */
2288   NULL,                       /* Local compute function.  */
2289   NULL,                       /* Init the solution specific data.  */
2290   NULL,                       /* Iterative solver.  */
2291   NULL,                       /* Confluence operator 0.  */
2292   NULL,                       /* Confluence operator n.  */
2293   NULL,                       /* Transfer function.  */
2294   df_chain_finalize,          /* Finalize function.  */
2295   df_chain_free,              /* Free all of the problem information.  */
2296   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2297   NULL,                       /* Debugging.  */
2298   df_chain_top_dump,          /* Debugging start block.  */
2299   df_chain_bottom_dump,       /* Debugging end block.  */
2300   NULL,                       /* Incremental solution verify start.  */
2301   NULL,                       /* Incremental solution verify end.  */
2302   &problem_RD,                /* Dependent problem.  */
2303   TV_DF_CHAIN,                /* Timing variable.  */
2304   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2305 };
2306
2307
2308 /* Create a new DATAFLOW instance and add it to an existing instance
2309    of DF.  The returned structure is what is used to get at the
2310    solution.  */
2311
2312 void
2313 df_chain_add_problem (enum df_chain_flags chain_flags)
2314 {
2315   df_add_problem (&problem_CHAIN);
2316   df_chain->local_flags = (unsigned int)chain_flags;
2317   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2318 }
2319
2320 #undef df_chain_problem_p
2321
2322 \f
2323 /*----------------------------------------------------------------------------
2324    This pass computes REG_DEAD and REG_UNUSED notes.
2325    ----------------------------------------------------------------------------*/
2326
2327 static void
2328 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2329 {
2330   df_note->optional_p = true;
2331 }
2332
2333 #ifdef REG_DEAD_DEBUGGING
2334 static void
2335 df_print_note (const char *prefix, rtx insn, rtx note)
2336 {
2337   if (dump_file)
2338     {
2339       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2340       print_rtl (dump_file, note);
2341       fprintf (dump_file, "\n");
2342     }
2343 }
2344 #endif
2345
2346
2347 /* After reg-stack, the x86 floating point stack regs are difficult to
2348    analyze because of all of the pushes, pops and rotations.  Thus, we
2349    just leave the notes alone. */
2350
2351 #ifdef STACK_REGS
2352 static inline bool
2353 df_ignore_stack_reg (int regno)
2354 {
2355   return regstack_completed
2356     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2357 }
2358 #else
2359 static inline bool
2360 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2361 {
2362   return false;
2363 }
2364 #endif
2365
2366
2367 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
2368    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
2369
2370 static void
2371 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
2372 {
2373   rtx *pprev = &REG_NOTES (insn);
2374   rtx link = *pprev;
2375   rtx dead = NULL;
2376   rtx unused = NULL;
2377
2378   while (link)
2379     {
2380       switch (REG_NOTE_KIND (link))
2381         {
2382         case REG_DEAD:
2383           /* After reg-stack, we need to ignore any unused notes
2384              for the stack registers.  */
2385           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2386             {
2387               pprev = &XEXP (link, 1);
2388               link = *pprev;
2389             }
2390           else
2391             {
2392               rtx next = XEXP (link, 1);
2393 #ifdef REG_DEAD_DEBUGGING
2394               df_print_note ("deleting: ", insn, link);
2395 #endif
2396               XEXP (link, 1) = dead;
2397               dead = link;
2398               *pprev = link = next;
2399             }
2400           break;
2401
2402         case REG_UNUSED:
2403           /* After reg-stack, we need to ignore any unused notes
2404              for the stack registers.  */
2405           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2406             {
2407               pprev = &XEXP (link, 1);
2408               link = *pprev;
2409             }
2410           else
2411             {
2412               rtx next = XEXP (link, 1);
2413 #ifdef REG_DEAD_DEBUGGING
2414               df_print_note ("deleting: ", insn, link);
2415 #endif
2416               XEXP (link, 1) = unused;
2417               unused = link;
2418               *pprev = link = next;
2419             }
2420           break;
2421
2422         default:
2423           pprev = &XEXP (link, 1);
2424           link = *pprev;
2425           break;
2426         }
2427     }
2428
2429   *old_dead_notes = dead;
2430   *old_unused_notes = unused;
2431 }
2432
2433
2434 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
2435    list, otherwise create a new one.  */
2436
2437 static inline rtx
2438 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
2439 {
2440   rtx this = old;
2441   rtx prev = NULL;
2442
2443   while (this)
2444     if (XEXP (this, 0) == reg)
2445       {
2446         if (prev)
2447           XEXP (prev, 1) = XEXP (this, 1);
2448         else
2449           old = XEXP (this, 1);
2450         XEXP (this, 1) = REG_NOTES (insn);
2451         REG_NOTES (insn) = this;
2452         return old;
2453       }
2454     else
2455       {
2456         prev = this;
2457         this = XEXP (this, 1);
2458       }
2459
2460   /* Did not find the note.  */
2461   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
2462   return old;
2463 }
2464
2465 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2466    arguments.  Return true if the register value described by MWS's
2467    mw_reg is known to be completely unused, and if mw_reg can therefore
2468    be used in a REG_UNUSED note.  */
2469
2470 static bool
2471 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2472                           bitmap live, bitmap artificial_uses)
2473 {
2474   unsigned int r;
2475
2476   /* If MWS describes a partial reference, create REG_UNUSED notes for
2477      individual hard registers.  */
2478   if (mws->flags & DF_REF_PARTIAL)
2479     return false;
2480
2481   /* Likewise if some part of the register is used.  */
2482   for (r = mws->start_regno; r <= mws->end_regno; r++)
2483     if (bitmap_bit_p (live, r)
2484         || bitmap_bit_p (artificial_uses, r))
2485       return false;
2486
2487   gcc_assert (REG_P (mws->mw_reg));
2488   return true;
2489 }
2490
2491 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2492    based on the bits in LIVE.  Do not generate notes for registers in
2493    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2494    not generated if the reg is both read and written by the
2495    instruction.
2496 */
2497
2498 static rtx
2499 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2500                             bitmap live, bitmap do_not_gen,
2501                             bitmap artificial_uses)
2502 {
2503   unsigned int r;
2504
2505 #ifdef REG_DEAD_DEBUGGING
2506   if (dump_file)
2507     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2508              mws->start_regno, mws->end_regno);
2509 #endif
2510
2511   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2512     {
2513       unsigned int regno = mws->start_regno;
2514       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
2515
2516 #ifdef REG_DEAD_DEBUGGING
2517       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2518 #endif
2519       bitmap_set_bit (do_not_gen, regno);
2520       /* Only do this if the value is totally dead.  */
2521     }
2522   else
2523     for (r = mws->start_regno; r <= mws->end_regno; r++)
2524       {
2525         if (!bitmap_bit_p (live, r)
2526             && !bitmap_bit_p (artificial_uses, r))
2527           {
2528             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
2529 #ifdef REG_DEAD_DEBUGGING
2530             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2531 #endif
2532           }
2533         bitmap_set_bit (do_not_gen, r);
2534       }
2535   return old;
2536 }
2537
2538
2539 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2540    arguments.  Return true if the register value described by MWS's
2541    mw_reg is known to be completely dead, and if mw_reg can therefore
2542    be used in a REG_DEAD note.  */
2543
2544 static bool
2545 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2546                         bitmap live, bitmap artificial_uses,
2547                         bitmap do_not_gen)
2548 {
2549   unsigned int r;
2550
2551   /* If MWS describes a partial reference, create REG_DEAD notes for
2552      individual hard registers.  */
2553   if (mws->flags & DF_REF_PARTIAL)
2554     return false;
2555
2556   /* Likewise if some part of the register is not dead.  */
2557   for (r = mws->start_regno; r <= mws->end_regno; r++)
2558     if (bitmap_bit_p (live, r)
2559         || bitmap_bit_p (artificial_uses, r)
2560         || bitmap_bit_p (do_not_gen, r))
2561       return false;
2562
2563   gcc_assert (REG_P (mws->mw_reg));
2564   return true;
2565 }
2566
2567 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2568    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2569    from being set if the instruction both reads and writes the
2570    register.  */
2571
2572 static rtx
2573 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2574                           bitmap live, bitmap do_not_gen,
2575                           bitmap artificial_uses)
2576 {
2577   unsigned int r;
2578
2579 #ifdef REG_DEAD_DEBUGGING
2580   if (dump_file)
2581     {
2582       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
2583                mws->start_regno, mws->end_regno);
2584       df_print_regset (dump_file, do_not_gen);
2585       fprintf (dump_file, "  live =");
2586       df_print_regset (dump_file, live);
2587       fprintf (dump_file, "  artificial uses =");
2588       df_print_regset (dump_file, artificial_uses);
2589     }
2590 #endif
2591
2592   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
2593     {
2594       /* Add a dead note for the entire multi word register.  */
2595       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
2596 #ifdef REG_DEAD_DEBUGGING
2597       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2598 #endif
2599     }
2600   else
2601     {
2602       for (r = mws->start_regno; r <= mws->end_regno; r++)
2603         if (!bitmap_bit_p (live, r)
2604             && !bitmap_bit_p (artificial_uses, r)
2605             && !bitmap_bit_p (do_not_gen, r))
2606           {
2607             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
2608 #ifdef REG_DEAD_DEBUGGING
2609             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2610 #endif
2611           }
2612     }
2613   return old;
2614 }
2615
2616
2617 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
2618    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
2619
2620 static rtx
2621 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
2622                        bitmap live, bitmap artificial_uses)
2623 {
2624   unsigned int dregno = DF_REF_REGNO (def);
2625
2626 #ifdef REG_DEAD_DEBUGGING
2627   if (dump_file)
2628     {
2629       fprintf (dump_file, "  regular looking at def ");
2630       df_ref_debug (def, dump_file);
2631     }
2632 #endif
2633
2634   if (!(bitmap_bit_p (live, dregno)
2635         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
2636         || bitmap_bit_p (artificial_uses, dregno)
2637         || df_ignore_stack_reg (dregno)))
2638     {
2639       rtx reg = (DF_REF_LOC (def))
2640                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
2641       old = df_set_note (REG_UNUSED, insn, old, reg);
2642 #ifdef REG_DEAD_DEBUGGING
2643       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
2644 #endif
2645     }
2646
2647   return old;
2648 }
2649
2650
2651 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
2652    info: lifetime, bb, and number of defs and uses for basic block
2653    BB.  The three bitvectors are scratch regs used here.  */
2654
2655 static void
2656 df_note_bb_compute (unsigned int bb_index,
2657                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
2658 {
2659   basic_block bb = BASIC_BLOCK (bb_index);
2660   rtx insn;
2661   struct df_ref **def_rec;
2662   struct df_ref **use_rec;
2663
2664   bitmap_copy (live, df_get_live_out (bb));
2665   bitmap_clear (artificial_uses);
2666
2667 #ifdef REG_DEAD_DEBUGGING
2668   if (dump_file)
2669     {
2670       fprintf (dump_file, "live at bottom ");
2671       df_print_regset (dump_file, live);
2672     }
2673 #endif
2674
2675   /* Process the artificial defs and uses at the bottom of the block
2676      to begin processing.  */
2677   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2678     {
2679       struct df_ref *def = *def_rec;
2680 #ifdef REG_DEAD_DEBUGGING
2681       if (dump_file)
2682         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
2683 #endif
2684
2685       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2686         bitmap_clear_bit (live, DF_REF_REGNO (def));
2687     }
2688
2689   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2690     {
2691       struct df_ref *use = *use_rec;
2692       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2693         {
2694           unsigned int regno = DF_REF_REGNO (use);
2695           bitmap_set_bit (live, regno);
2696
2697           /* Notes are not generated for any of the artificial registers
2698              at the bottom of the block.  */
2699           bitmap_set_bit (artificial_uses, regno);
2700         }
2701     }
2702
2703 #ifdef REG_DEAD_DEBUGGING
2704   if (dump_file)
2705     {
2706       fprintf (dump_file, "live before artificials out ");
2707       df_print_regset (dump_file, live);
2708     }
2709 #endif
2710
2711   FOR_BB_INSNS_REVERSE (bb, insn)
2712     {
2713       unsigned int uid = INSN_UID (insn);
2714       struct df_mw_hardreg **mws_rec;
2715       rtx old_dead_notes;
2716       rtx old_unused_notes;
2717
2718       if (!INSN_P (insn))
2719         continue;
2720
2721       bitmap_clear (do_not_gen);
2722       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
2723
2724       /* Process the defs.  */
2725       if (CALL_P (insn))
2726         {
2727 #ifdef REG_DEAD_DEBUGGING
2728           if (dump_file)
2729             {
2730               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
2731               df_print_regset (dump_file, live);
2732             }
2733 #endif
2734           /* We only care about real sets for calls.  Clobbers cannot
2735              be depended on to really die.  */
2736           mws_rec = DF_INSN_UID_MWS (uid);
2737           while (*mws_rec)
2738             {
2739               struct df_mw_hardreg *mws = *mws_rec;
2740               if ((mws->type == DF_REF_REG_DEF)
2741                   && !df_ignore_stack_reg (mws->start_regno))
2742                 old_unused_notes
2743                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2744                                                 mws, live, do_not_gen,
2745                                                 artificial_uses);
2746               mws_rec++;
2747             }
2748
2749           /* All of the defs except the return value are some sort of
2750              clobber.  This code is for the return.  */
2751           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2752             {
2753               struct df_ref *def = *def_rec;
2754               unsigned int dregno = DF_REF_REGNO (def);
2755               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2756                 {
2757                   old_unused_notes
2758                     = df_create_unused_note (insn, old_unused_notes,
2759                                              def, live, artificial_uses);
2760                   bitmap_set_bit (do_not_gen, dregno);
2761                 }
2762
2763               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2764                 bitmap_clear_bit (live, dregno);
2765             }
2766         }
2767       else
2768         {
2769           /* Regular insn.  */
2770           mws_rec = DF_INSN_UID_MWS (uid);
2771           while (*mws_rec)
2772             {
2773               struct df_mw_hardreg *mws = *mws_rec;
2774               if (mws->type == DF_REF_REG_DEF)
2775                 old_unused_notes
2776                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2777                                                 mws, live, do_not_gen,
2778                                                 artificial_uses);
2779               mws_rec++;
2780             }
2781
2782           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2783             {
2784               struct df_ref *def = *def_rec;
2785               unsigned int dregno = DF_REF_REGNO (def);
2786               old_unused_notes
2787                 = df_create_unused_note (insn, old_unused_notes,
2788                                          def, live, artificial_uses);
2789
2790               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2791                 bitmap_set_bit (do_not_gen, dregno);
2792
2793               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2794                 bitmap_clear_bit (live, dregno);
2795             }
2796         }
2797
2798       /* Process the uses.  */
2799       mws_rec = DF_INSN_UID_MWS (uid);
2800       while (*mws_rec)
2801         {
2802           struct df_mw_hardreg *mws = *mws_rec;
2803           if ((mws->type != DF_REF_REG_DEF)
2804               && !df_ignore_stack_reg (mws->start_regno))
2805             old_dead_notes
2806               = df_set_dead_notes_for_mw (insn, old_dead_notes,
2807                                           mws, live, do_not_gen,
2808                                           artificial_uses);
2809           mws_rec++;
2810         }
2811
2812       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2813         {
2814           struct df_ref *use = *use_rec;
2815           unsigned int uregno = DF_REF_REGNO (use);
2816
2817 #ifdef REG_DEAD_DEBUGGING
2818           if (dump_file)
2819             {
2820               fprintf (dump_file, "  regular looking at use ");
2821               df_ref_debug (use, dump_file);
2822             }
2823 #endif
2824           if (!bitmap_bit_p (live, uregno))
2825             {
2826               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
2827                    && (!bitmap_bit_p (do_not_gen, uregno))
2828                    && (!bitmap_bit_p (artificial_uses, uregno))
2829                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
2830                    && (!df_ignore_stack_reg (uregno)))
2831                 {
2832                   rtx reg = (DF_REF_LOC (use))
2833                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
2834                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
2835
2836 #ifdef REG_DEAD_DEBUGGING
2837                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
2838 #endif
2839                 }
2840               /* This register is now live.  */
2841               bitmap_set_bit (live, uregno);
2842             }
2843         }
2844
2845       while (old_unused_notes)
2846         {
2847           rtx next = XEXP (old_unused_notes, 1);
2848           free_EXPR_LIST_node (old_unused_notes);
2849           old_unused_notes = next;
2850         }
2851       while (old_dead_notes)
2852         {
2853           rtx next = XEXP (old_dead_notes, 1);
2854           free_EXPR_LIST_node (old_dead_notes);
2855           old_dead_notes = next;
2856         }
2857     }
2858 }
2859
2860
2861 /* Compute register info: lifetime, bb, and number of defs and uses.  */
2862 static void
2863 df_note_compute (bitmap all_blocks)
2864 {
2865   unsigned int bb_index;
2866   bitmap_iterator bi;
2867   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
2868   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
2869   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
2870
2871 #ifdef REG_DEAD_DEBUGGING
2872   if (dump_file)
2873     print_rtl_with_bb (dump_file, get_insns());
2874 #endif
2875
2876   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2877   {
2878     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
2879   }
2880
2881   BITMAP_FREE (live);
2882   BITMAP_FREE (do_not_gen);
2883   BITMAP_FREE (artificial_uses);
2884 }
2885
2886
2887 /* Free all storage associated with the problem.  */
2888
2889 static void
2890 df_note_free (void)
2891 {
2892   free (df_note);
2893 }
2894
2895
2896 /* All of the information associated every instance of the problem.  */
2897
2898 static struct df_problem problem_NOTE =
2899 {
2900   DF_NOTE,                    /* Problem id.  */
2901   DF_NONE,                    /* Direction.  */
2902   df_note_alloc,              /* Allocate the problem specific data.  */
2903   NULL,                       /* Reset global information.  */
2904   NULL,                       /* Free basic block info.  */
2905   df_note_compute,            /* Local compute function.  */
2906   NULL,                       /* Init the solution specific data.  */
2907   NULL,                       /* Iterative solver.  */
2908   NULL,                       /* Confluence operator 0.  */
2909   NULL,                       /* Confluence operator n.  */
2910   NULL,                       /* Transfer function.  */
2911   NULL,                       /* Finalize function.  */
2912   df_note_free,               /* Free all of the problem information.  */
2913   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
2914   NULL,                       /* Debugging.  */
2915   NULL,                       /* Debugging start block.  */
2916   NULL,                       /* Debugging end block.  */
2917   NULL,                       /* Incremental solution verify start.  */
2918   NULL,                       /* Incremental solution verify end.  */
2919
2920   /* Technically this is only dependent on the live registers problem
2921      but it will produce information if built one of uninitialized
2922      register problems (UR, UREC) is also run.  */
2923   &problem_LR,                /* Dependent problem.  */
2924   TV_DF_NOTE,                 /* Timing variable.  */
2925   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2926 };
2927
2928
2929 /* Create a new DATAFLOW instance and add it to an existing instance
2930    of DF.  The returned structure is what is used to get at the
2931    solution.  */
2932
2933 void
2934 df_note_add_problem (void)
2935 {
2936   df_add_problem (&problem_NOTE);
2937 }
2938
2939
2940
2941 \f
2942 /*----------------------------------------------------------------------------
2943    Functions for simulating the effects of single insns.
2944
2945    You can either simulate in the forwards direction, starting from
2946    the top of a block or the backwards direction from the end of the
2947    block.  The main difference is that if you go forwards, the uses
2948    are examined first then the defs, and if you go backwards, the defs
2949    are examined first then the uses.
2950
2951    If you start at the top of the block, use one of DF_LIVE_IN or
2952    DF_LR_IN.  If you start at the bottom of the block use one of
2953    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
2954    THEY WILL BE DESTROYED.
2955
2956 ----------------------------------------------------------------------------*/
2957
2958
2959 /* Find the set of DEFs for INSN.  */
2960
2961 void
2962 df_simulate_find_defs (rtx insn, bitmap defs)
2963 {
2964   struct df_ref **def_rec;
2965   unsigned int uid = INSN_UID (insn);
2966
2967   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2968     {
2969       struct df_ref *def = *def_rec;
2970       /* If the def is to only part of the reg, it does
2971          not kill the other defs that reach here.  */
2972       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2973         bitmap_set_bit (defs, DF_REF_REGNO (def));
2974     }
2975 }
2976
2977
2978 /* Simulate the effects of the defs of INSN on LIVE.  */
2979
2980 void
2981 df_simulate_defs (rtx insn, bitmap live)
2982 {
2983   struct df_ref **def_rec;
2984   unsigned int uid = INSN_UID (insn);
2985
2986   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2987     {
2988       struct df_ref *def = *def_rec;
2989       unsigned int dregno = DF_REF_REGNO (def);
2990
2991       /* If the def is to only part of the reg, it does
2992          not kill the other defs that reach here.  */
2993       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2994         bitmap_clear_bit (live, dregno);
2995     }
2996 }
2997
2998
2999 /* Simulate the effects of the uses of INSN on LIVE.  */
3000
3001 void
3002 df_simulate_uses (rtx insn, bitmap live)
3003 {
3004   struct df_ref **use_rec;
3005   unsigned int uid = INSN_UID (insn);
3006
3007   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3008     {
3009       struct df_ref *use = *use_rec;
3010       /* Add use to set of uses in this BB.  */
3011       bitmap_set_bit (live, DF_REF_REGNO (use));
3012     }
3013 }
3014
3015
3016 /* Add back the always live regs in BB to LIVE.  */
3017
3018 static inline void
3019 df_simulate_fixup_sets (basic_block bb, bitmap live)
3020 {
3021   /* These regs are considered always live so if they end up dying
3022      because of some def, we need to bring the back again.  */
3023   if (bb_has_eh_pred (bb))
3024     bitmap_ior_into (live, df->eh_block_artificial_uses);
3025   else
3026     bitmap_ior_into (live, df->regular_block_artificial_uses);
3027 }
3028
3029
3030 /* Apply the artificial uses and defs at the top of BB in a forwards
3031    direction.  */
3032
3033 void
3034 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3035 {
3036   struct df_ref **def_rec;
3037   struct df_ref **use_rec;
3038   int bb_index = bb->index;
3039
3040   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3041     {
3042       struct df_ref *use = *use_rec;
3043       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3044         bitmap_set_bit (live, DF_REF_REGNO (use));
3045     }
3046
3047   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3048     {
3049       struct df_ref *def = *def_rec;
3050       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3051         bitmap_clear_bit (live, DF_REF_REGNO (def));
3052     }
3053 }
3054
3055
3056 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3057
3058 void
3059 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3060 {
3061   if (! INSN_P (insn))
3062     return;
3063
3064   df_simulate_uses (insn, live);
3065   df_simulate_defs (insn, live);
3066   df_simulate_fixup_sets (bb, live);
3067 }
3068
3069
3070 /* Apply the artificial uses and defs at the end of BB in a backwards
3071    direction.  */
3072
3073 void
3074 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3075 {
3076   struct df_ref **def_rec;
3077   struct df_ref **use_rec;
3078   int bb_index = bb->index;
3079
3080   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3081     {
3082       struct df_ref *def = *def_rec;
3083       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3084         bitmap_clear_bit (live, DF_REF_REGNO (def));
3085     }
3086
3087   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3088     {
3089       struct df_ref *use = *use_rec;
3090       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3091         bitmap_set_bit (live, DF_REF_REGNO (use));
3092     }
3093 }
3094
3095
3096 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3097
3098 void
3099 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3100 {
3101   if (! INSN_P (insn))
3102     return;
3103
3104   df_simulate_defs (insn, live);
3105   df_simulate_uses (insn, live);
3106   df_simulate_fixup_sets (bb, live);
3107 }
3108
3109