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