gcc/df-problems.c

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