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