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       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1393         {
1394           struct df_ref *def = *def_rec;
1395           /* If the def is to only part of the reg, it does
1396              not kill the other defs that reach here.  */
1397           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
1398             {
1399               unsigned int dregno = DF_REF_REGNO (def);
1400               bitmap_set_bit (bb_info->def, dregno);
1401               bitmap_clear_bit (bb_info->use, dregno);
1402             }
1403         }
1404
1405       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1406         {
1407           struct df_ref *use = *use_rec;
1408           /* Add use to set of uses in this BB.  */
1409           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1410         }
1411     }
1412   /* Process the registers set in an exception handler.  */
1413   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1414     {
1415       struct df_ref *def = *def_rec;
1416       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1417           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
1418         {
1419           unsigned int dregno = DF_REF_REGNO (def);
1420           if (bb_info->adef == NULL)
1421             {
1422               gcc_assert (bb_info->ause == NULL);
1423               gcc_assert (bb_info->top == bb_info->in);
1424               bb_info->adef = BITMAP_ALLOC (NULL);
1425               bb_info->ause = BITMAP_ALLOC (NULL);
1426               bb_info->top = BITMAP_ALLOC (NULL);
1427             }
1428           bitmap_set_bit (bb_info->adef, dregno);
1429         }
1430     }
1431
1432 #ifdef EH_USES
1433   /* Process the uses that are live into an exception handler.  */
1434   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
1435     {
1436       struct df_ref *use = *use_rec;
1437       /* Add use to set of uses in this BB.  */
1438       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
1439         {
1440           if (bb_info->adef == NULL)
1441             {
1442               gcc_assert (bb_info->ause == NULL);
1443               gcc_assert (bb_info->top == bb_info->in);
1444               bb_info->adef = BITMAP_ALLOC (NULL);
1445               bb_info->ause = BITMAP_ALLOC (NULL);
1446               bb_info->top = BITMAP_ALLOC (NULL);
1447             }
1448           bitmap_set_bit (bb_info->ause, DF_REF_REGNO (use));
1449         }
1450     }
1451 #endif
1452
1453   /* If the df_live problem is not defined, such as at -O0 and -O1, we
1454      still need to keep the luids up to date.  This is normally done
1455      in the df_live problem since this problem has a forwards
1456      scan.  */
1457   if (!df_live)
1458     df_recompute_luids (bb);
1459 }
1460
1461
1462 /* Compute local live register info for each basic block within BLOCKS.  */
1463
1464 static void
1465 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1466 {
1467   unsigned int bb_index;
1468   bitmap_iterator bi;
1469
1470   bitmap_clear (df->hardware_regs_used);
1471
1472   /* The all-important stack pointer must always be live.  */
1473   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
1474
1475   /* Before reload, there are a few registers that must be forced
1476      live everywhere -- which might not already be the case for
1477      blocks within infinite loops.  */
1478   if (!reload_completed)
1479     {
1480       /* Any reference to any pseudo before reload is a potential
1481          reference of the frame pointer.  */
1482       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
1483
1484 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1485       /* Pseudos with argument area equivalences may require
1486          reloading via the argument pointer.  */
1487       if (fixed_regs[ARG_POINTER_REGNUM])
1488         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
1489 #endif
1490
1491       /* Any constant, or pseudo with constant equivalences, may
1492          require reloading from memory using the pic register.  */
1493       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1494           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1495         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
1496     }
1497
1498   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
1499     {
1500       if (bb_index == EXIT_BLOCK)
1501         {
1502           /* The exit block is special for this problem and its bits are
1503              computed from thin air.  */
1504           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
1505           bitmap_copy (bb_info->use, df->exit_block_uses);
1506         }
1507       else
1508         df_lr_bb_local_compute (bb_index);
1509     }
1510
1511   bitmap_clear (df_lr->out_of_date_transfer_functions);
1512 }
1513
1514
1515 /* Initialize the solution vectors.  */
1516
1517 static void
1518 df_lr_init (bitmap all_blocks)
1519 {
1520   unsigned int bb_index;
1521   bitmap_iterator bi;
1522
1523   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1524     {
1525       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1526       bitmap_copy (bb_info->in, bb_info->use);
1527       bitmap_clear (bb_info->out);
1528     }
1529 }
1530
1531
1532 /* Confluence function that processes infinite loops.  This might be a
1533    noreturn function that throws.  And even if it isn't, getting the
1534    unwind info right helps debugging.  */
1535 static void
1536 df_lr_confluence_0 (basic_block bb)
1537 {
1538   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
1539   if (bb != EXIT_BLOCK_PTR)
1540     bitmap_copy (op1, df->hardware_regs_used);
1541 }
1542
1543
1544 /* Confluence function that ignores fake edges.  */
1545
1546 static void
1547 df_lr_confluence_n (edge e)
1548 {
1549   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
1550   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
1551
1552   /* Call-clobbered registers die across exception and call edges.  */
1553   /* ??? Abnormal call edges ignored for the moment, as this gets
1554      confused by sibling call edges, which crashes reg-stack.  */
1555   if (e->flags & EDGE_EH)
1556     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1557   else
1558     bitmap_ior_into (op1, op2);
1559
1560   bitmap_ior_into (op1, df->hardware_regs_used);
1561 }
1562
1563
1564 /* Transfer function.  */
1565
1566 static bool
1567 df_lr_transfer_function (int bb_index)
1568 {
1569   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1570   bitmap in = bb_info->in;
1571   bitmap out = bb_info->out;
1572   bitmap use = bb_info->use;
1573   bitmap def = bb_info->def;
1574   bitmap top = bb_info->top;
1575   bitmap ause = bb_info->ause;
1576   bitmap adef = bb_info->adef;
1577   bool changed;
1578
1579   changed = bitmap_ior_and_compl (top, use, out, def);
1580   if (in != top)
1581     {
1582       gcc_assert (ause && adef);
1583       changed |= bitmap_ior_and_compl (in, ause, top, adef);
1584     }
1585
1586   return changed;
1587 }
1588
1589
1590 /* Run the fast dce as a side effect of building LR.  */
1591
1592 static void
1593 df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1594 {
1595   if (df->changeable_flags & DF_LR_RUN_DCE)
1596     {
1597       run_fast_df_dce ();
1598       if (df_lr->problem_data && df_lr->solutions_dirty)
1599         {
1600           /* If we are here, then it is because we are both verifying
1601           the solution and the dce changed the function.  In that case
1602           the verification info built will be wrong.  So we leave the
1603           dirty flag true so that the verifier will skip the checking
1604           part and just clean up.*/
1605           df_lr->solutions_dirty = true;
1606         }
1607       else
1608         df_lr->solutions_dirty = false;
1609     }
1610   else
1611     df_lr->solutions_dirty = false;
1612 }
1613
1614
1615 /* Free all storage associated with the problem.  */
1616
1617 static void
1618 df_lr_free (void)
1619 {
1620   if (df_lr->block_info)
1621     {
1622       unsigned int i;
1623       for (i = 0; i < df_lr->block_info_size; i++)
1624         {
1625           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1626           if (bb_info)
1627             {
1628               BITMAP_FREE (bb_info->use);
1629               BITMAP_FREE (bb_info->def);
1630               if (bb_info->in == bb_info->top)
1631                 bb_info->top = NULL;
1632               else
1633                 {
1634                   BITMAP_FREE (bb_info->top);
1635                   BITMAP_FREE (bb_info->ause);
1636                   BITMAP_FREE (bb_info->adef);
1637                 }
1638               BITMAP_FREE (bb_info->in);
1639               BITMAP_FREE (bb_info->out);
1640             }
1641         }
1642       free_alloc_pool (df_lr->block_pool);
1643
1644       df_lr->block_info_size = 0;
1645       free (df_lr->block_info);
1646     }
1647
1648   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1649   free (df_lr);
1650 }
1651
1652
1653 /* Debugging info at top of bb.  */
1654
1655 static void
1656 df_lr_top_dump (basic_block bb, FILE *file)
1657 {
1658   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1659   struct df_lr_problem_data *problem_data;
1660   if (!bb_info || !bb_info->in)
1661     return;
1662
1663   fprintf (file, ";; lr  in  \t");
1664   df_print_regset (file, bb_info->in);
1665   if (df_lr->problem_data)
1666     {
1667       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1668       fprintf (file, ";;  old in  \t");
1669       df_print_regset (file, problem_data->in[bb->index]);
1670     }
1671   fprintf (file, ";; lr  use \t");
1672   df_print_regset (file, bb_info->use);
1673   fprintf (file, ";; lr  def \t");
1674   df_print_regset (file, bb_info->def);
1675 }
1676
1677
1678 /* Debugging info at bottom of bb.  */
1679
1680 static void
1681 df_lr_bottom_dump (basic_block bb, FILE *file)
1682 {
1683   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1684   struct df_lr_problem_data *problem_data;
1685   if (!bb_info || !bb_info->out)
1686     return;
1687
1688   fprintf (file, ";; lr  out \t");
1689   df_print_regset (file, bb_info->out);
1690   if (df_lr->problem_data)
1691     {
1692       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1693       fprintf (file, ";;  old out  \t");
1694       df_print_regset (file, problem_data->out[bb->index]);
1695     }
1696 }
1697
1698
1699 /* Build the datastructure to verify that the solution to the dataflow
1700    equations is not dirty.  */
1701
1702 static void
1703 df_lr_verify_solution_start (void)
1704 {
1705   basic_block bb;
1706   struct df_lr_problem_data *problem_data;
1707   if (df_lr->solutions_dirty)
1708     {
1709       df_lr->problem_data = NULL;
1710       return;
1711     }
1712
1713   /* Set it true so that the solution is recomputed.  */
1714   df_lr->solutions_dirty = true;
1715
1716   problem_data = XNEW (struct df_lr_problem_data);
1717   df_lr->problem_data = problem_data;
1718   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1719   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1720
1721   FOR_ALL_BB (bb)
1722     {
1723       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1724       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1725       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1726       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1727     }
1728 }
1729
1730
1731 /* Compare the saved datastructure and the new solution to the dataflow
1732    equations.  */
1733
1734 static void
1735 df_lr_verify_solution_end (void)
1736 {
1737   struct df_lr_problem_data *problem_data;
1738   basic_block bb;
1739
1740   if (df_lr->problem_data == NULL)
1741     return;
1742
1743   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1744
1745   if (df_lr->solutions_dirty)
1746     /* Do not check if the solution is still dirty.  See the comment
1747        in df_lr_local_finalize for details.  */
1748     df_lr->solutions_dirty = false;
1749   else
1750     FOR_ALL_BB (bb)
1751       {
1752         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1753             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1754           {
1755             /*df_dump (stderr);*/
1756             gcc_unreachable ();
1757           }
1758       }
1759
1760   /* Cannot delete them immediately because you may want to dump them
1761      if the comparison fails.  */
1762   FOR_ALL_BB (bb)
1763     {
1764       BITMAP_FREE (problem_data->in[bb->index]);
1765       BITMAP_FREE (problem_data->out[bb->index]);
1766     }
1767
1768   free (problem_data->in);
1769   free (problem_data->out);
1770   free (problem_data);
1771   df_lr->problem_data = NULL;
1772 }
1773
1774
1775 /* All of the information associated with every instance of the problem.  */
1776
1777 static struct df_problem problem_LR =
1778 {
1779   DF_LR,                      /* Problem id.  */
1780   DF_BACKWARD,                /* Direction.  */
1781   df_lr_alloc,                /* Allocate the problem specific data.  */
1782   df_lr_reset,                /* Reset global information.  */
1783   df_lr_free_bb_info,         /* Free basic block info.  */
1784   df_lr_local_compute,        /* Local compute function.  */
1785   df_lr_init,                 /* Init the solution specific data.  */
1786   df_worklist_dataflow,       /* Worklist solver.  */
1787   df_lr_confluence_0,         /* Confluence operator 0.  */
1788   df_lr_confluence_n,         /* Confluence operator n.  */
1789   df_lr_transfer_function,    /* Transfer function.  */
1790   df_lr_local_finalize,       /* Finalize function.  */
1791   df_lr_free,                 /* Free all of the problem information.  */
1792   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1793   NULL,                       /* Debugging.  */
1794   df_lr_top_dump,             /* Debugging start block.  */
1795   df_lr_bottom_dump,          /* Debugging end block.  */
1796   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1797   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1798   NULL,                       /* Dependent problem.  */
1799   TV_DF_LR,                   /* Timing variable.  */
1800   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1801 };
1802
1803
1804 /* Create a new DATAFLOW instance and add it to an existing instance
1805    of DF.  The returned structure is what is used to get at the
1806    solution.  */
1807
1808 void
1809 df_lr_add_problem (void)
1810 {
1811   df_add_problem (&problem_LR);
1812   /* These will be initialized when df_scan_blocks processes each
1813      block.  */
1814   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1815 }
1816
1817
1818 /* Verify that all of the lr related info is consistent and
1819    correct.  */
1820
1821 void
1822 df_lr_verify_transfer_functions (void)
1823 {
1824   basic_block bb;
1825   bitmap saved_def;
1826   bitmap saved_use;
1827   bitmap saved_adef;
1828   bitmap saved_ause;
1829   bitmap all_blocks;
1830   bool need_as;
1831
1832   if (!df)
1833     return;
1834
1835   saved_def = BITMAP_ALLOC (NULL);
1836   saved_use = BITMAP_ALLOC (NULL);
1837   saved_adef = BITMAP_ALLOC (NULL);
1838   saved_ause = BITMAP_ALLOC (NULL);
1839   all_blocks = BITMAP_ALLOC (NULL);
1840
1841   FOR_ALL_BB (bb)
1842     {
1843       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1844       bitmap_set_bit (all_blocks, bb->index);
1845
1846       if (bb_info)
1847         {
1848           /* Make a copy of the transfer functions and then compute
1849              new ones to see if the transfer functions have
1850              changed.  */
1851           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1852                              bb->index))
1853             {
1854               bitmap_copy (saved_def, bb_info->def);
1855               bitmap_copy (saved_use, bb_info->use);
1856               bitmap_clear (bb_info->def);
1857               bitmap_clear (bb_info->use);
1858
1859               if (bb_info->adef)
1860                 {
1861                   need_as = true;
1862                   bitmap_copy (saved_adef, bb_info->adef);
1863                   bitmap_copy (saved_ause, bb_info->ause);
1864                   bitmap_clear (bb_info->adef);
1865                   bitmap_clear (bb_info->ause);
1866                 }
1867               else
1868                 need_as = false;
1869
1870               df_lr_bb_local_compute (bb->index);
1871               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1872               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1873
1874               if (need_as)
1875                 {
1876                   gcc_assert (bb_info->adef);
1877                   gcc_assert (bb_info->ause);
1878                   gcc_assert (bitmap_equal_p (saved_adef, bb_info->adef));
1879                   gcc_assert (bitmap_equal_p (saved_ause, bb_info->ause));
1880                 }
1881               else
1882                 {
1883                   gcc_assert (!bb_info->adef);
1884                   gcc_assert (!bb_info->ause);
1885                 }
1886             }
1887         }
1888       else
1889         {
1890           /* If we do not have basic block info, the block must be in
1891              the list of dirty blocks or else some one has added a
1892              block behind our backs. */
1893           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1894                                     bb->index));
1895         }
1896       /* Make sure no one created a block without following
1897          procedures.  */
1898       gcc_assert (df_scan_get_bb_info (bb->index));
1899     }
1900
1901   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1902   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1903                                          all_blocks));
1904
1905   BITMAP_FREE (saved_def);
1906   BITMAP_FREE (saved_use);
1907   BITMAP_FREE (saved_adef);
1908   BITMAP_FREE (saved_ause);
1909   BITMAP_FREE (all_blocks);
1910 }
1911
1912
1913 \f
1914 /*----------------------------------------------------------------------------
1915    COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
1916
1917    First find the set of uses for registers that are reachable from
1918    the entry block without passing thru a definition.  In and out
1919    bitvectors are built for each basic block.  The regnum is used to
1920    index into these sets.  See df.h for details.
1921
1922    Then the in and out sets here are the anded results of the in and
1923    out sets from the lr and ur
1924    problems.
1925 ----------------------------------------------------------------------------*/
1926
1927 /* Private data used to verify the solution for this problem.  */
1928 struct df_live_problem_data
1929 {
1930   bitmap *in;
1931   bitmap *out;
1932 };
1933
1934
1935 /* Set basic block info.  */
1936
1937 static void
1938 df_live_set_bb_info (unsigned int index,
1939                    struct df_live_bb_info *bb_info)
1940 {
1941   gcc_assert (df_live);
1942   gcc_assert (index < df_live->block_info_size);
1943   df_live->block_info[index] = bb_info;
1944 }
1945
1946
1947 /* Free basic block info.  */
1948
1949 static void
1950 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1951                     void *vbb_info)
1952 {
1953   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1954   if (bb_info)
1955     {
1956       BITMAP_FREE (bb_info->gen);
1957       BITMAP_FREE (bb_info->kill);
1958       BITMAP_FREE (bb_info->in);
1959       BITMAP_FREE (bb_info->out);
1960       pool_free (df_live->block_pool, bb_info);
1961     }
1962 }
1963
1964
1965 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1966    not touched unless the block is new.  */
1967
1968 static void
1969 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1970 {
1971   unsigned int bb_index;
1972   bitmap_iterator bi;
1973
1974   if (!df_live->block_pool)
1975     df_live->block_pool = create_alloc_pool ("df_live_block pool",
1976                                            sizeof (struct df_live_bb_info), 100);
1977
1978   df_grow_bb_info (df_live);
1979
1980   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1981     {
1982       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1983       if (bb_info)
1984         {
1985           bitmap_clear (bb_info->kill);
1986           bitmap_clear (bb_info->gen);
1987         }
1988       else
1989         {
1990           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1991           df_live_set_bb_info (bb_index, bb_info);
1992           bb_info->kill = BITMAP_ALLOC (NULL);
1993           bb_info->gen = BITMAP_ALLOC (NULL);
1994           bb_info->in = BITMAP_ALLOC (NULL);
1995           bb_info->out = BITMAP_ALLOC (NULL);
1996         }
1997     }
1998   df_live->optional_p = (optimize <= 1);
1999 }
2000
2001
2002 /* Reset the global solution for recalculation.  */
2003
2004 static void
2005 df_live_reset (bitmap all_blocks)
2006 {
2007   unsigned int bb_index;
2008   bitmap_iterator bi;
2009
2010   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2011     {
2012       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
2013       gcc_assert (bb_info);
2014       bitmap_clear (bb_info->in);
2015       bitmap_clear (bb_info->out);
2016     }
2017 }
2018
2019
2020 /* Compute local uninitialized register info for basic block BB.  */
2021
2022 static void
2023 df_live_bb_local_compute (unsigned int bb_index)
2024 {
2025   basic_block bb = BASIC_BLOCK (bb_index);
2026   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2027   rtx insn;
2028   struct df_ref **def_rec;
2029   int luid = 0;
2030
2031   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2032     {
2033       struct df_ref *def = *def_rec;
2034       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2035         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2036     }
2037
2038   FOR_BB_INSNS (bb, insn)
2039     {
2040       unsigned int uid = INSN_UID (insn);
2041       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2042
2043       /* Inserting labels does not always trigger the incremental
2044          rescanning.  */
2045       if (!insn_info)
2046         {
2047           gcc_assert (!INSN_P (insn));
2048           df_insn_create_insn_record (insn);
2049         }
2050
2051       DF_INSN_LUID (insn) = luid;
2052       if (!INSN_P (insn))
2053         continue;
2054
2055       luid++;
2056       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2057         {
2058           struct df_ref *def = *def_rec;
2059           unsigned int regno = DF_REF_REGNO (def);
2060
2061           if (DF_REF_FLAGS_IS_SET (def,
2062                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2063             /* All partial or conditional def
2064                seen are included in the gen set. */
2065             bitmap_set_bit (bb_info->gen, regno);
2066           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
2067             /* Only must clobbers for the entire reg destroy the
2068                value.  */
2069             bitmap_set_bit (bb_info->kill, regno);
2070           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2071             bitmap_set_bit (bb_info->gen, regno);
2072         }
2073     }
2074
2075   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2076     {
2077       struct df_ref *def = *def_rec;
2078       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2079         bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
2080     }
2081 }
2082
2083
2084 /* Compute local uninitialized register info.  */
2085
2086 static void
2087 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2088 {
2089   unsigned int bb_index;
2090   bitmap_iterator bi;
2091
2092   df_grow_insn_info ();
2093
2094   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
2095                             0, bb_index, bi)
2096     {
2097       df_live_bb_local_compute (bb_index);
2098     }
2099
2100   bitmap_clear (df_live->out_of_date_transfer_functions);
2101 }
2102
2103
2104 /* Initialize the solution vectors.  */
2105
2106 static void
2107 df_live_init (bitmap all_blocks)
2108 {
2109   unsigned int bb_index;
2110   bitmap_iterator bi;
2111
2112   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2113     {
2114       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2115
2116       bitmap_copy (bb_info->out, bb_info->gen);
2117       bitmap_clear (bb_info->in);
2118     }
2119 }
2120
2121 /* Confluence function that ignores fake edges.  */
2122
2123 static void
2124 df_live_confluence_n (edge e)
2125 {
2126   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
2127   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
2128
2129   if (e->flags & EDGE_FAKE)
2130     return;
2131
2132   bitmap_ior_into (op1, op2);
2133 }
2134
2135
2136 /* Transfer function.  */
2137
2138 static bool
2139 df_live_transfer_function (int bb_index)
2140 {
2141   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
2142   bitmap in = bb_info->in;
2143   bitmap out = bb_info->out;
2144   bitmap gen = bb_info->gen;
2145   bitmap kill = bb_info->kill;
2146
2147   return bitmap_ior_and_compl (out, gen, in, kill);
2148 }
2149
2150
2151 /* And the LR and UR info to produce the LIVE info.  */
2152
2153 static void
2154 df_live_local_finalize (bitmap all_blocks)
2155 {
2156
2157   if (df_live->solutions_dirty)
2158     {
2159       bitmap_iterator bi;
2160       unsigned int bb_index;
2161
2162       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2163         {
2164           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2165           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
2166
2167           /* No register may reach a location where it is not used.  Thus
2168              we trim the rr result to the places where it is used.  */
2169           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
2170           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
2171         }
2172
2173       df_live->solutions_dirty = false;
2174     }
2175 }
2176
2177
2178 /* Free all storage associated with the problem.  */
2179
2180 static void
2181 df_live_free (void)
2182 {
2183   if (df_live->block_info)
2184     {
2185       unsigned int i;
2186
2187       for (i = 0; i < df_live->block_info_size; i++)
2188         {
2189           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
2190           if (bb_info)
2191             {
2192               BITMAP_FREE (bb_info->gen);
2193               BITMAP_FREE (bb_info->kill);
2194               BITMAP_FREE (bb_info->in);
2195               BITMAP_FREE (bb_info->out);
2196             }
2197         }
2198
2199       free_alloc_pool (df_live->block_pool);
2200       df_live->block_info_size = 0;
2201       free (df_live->block_info);
2202     }
2203   BITMAP_FREE (df_live->out_of_date_transfer_functions);
2204   free (df_live);
2205 }
2206
2207
2208 /* Debugging info at top of bb.  */
2209
2210 static void
2211 df_live_top_dump (basic_block bb, FILE *file)
2212 {
2213   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2214   struct df_live_problem_data *problem_data;
2215
2216   if (!bb_info || !bb_info->in)
2217     return;
2218
2219   fprintf (file, ";; live  in  \t");
2220   df_print_regset (file, bb_info->in);
2221   if (df_live->problem_data)
2222     {
2223       problem_data = (struct df_live_problem_data *)df_live->problem_data;
2224       fprintf (file, ";;  old in  \t");
2225       df_print_regset (file, problem_data->in[bb->index]);
2226     }
2227   fprintf (file, ";; live  gen \t");
2228   df_print_regset (file, bb_info->gen);
2229   fprintf (file, ";; live  kill\t");
2230   df_print_regset (file, bb_info->kill);
2231 }
2232
2233
2234 /* Debugging info at bottom of bb.  */
2235
2236 static void
2237 df_live_bottom_dump (basic_block bb, FILE *file)
2238 {
2239   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2240   struct df_live_problem_data *problem_data;
2241
2242   if (!bb_info || !bb_info->out)
2243     return;
2244
2245   fprintf (file, ";; live  out \t");
2246   df_print_regset (file, bb_info->out);
2247   if (df_live->problem_data)
2248     {
2249       problem_data = (struct df_live_problem_data *)df_live->problem_data;
2250       fprintf (file, ";;  old out  \t");
2251       df_print_regset (file, problem_data->out[bb->index]);
2252     }
2253 }
2254
2255
2256 /* Build the datastructure to verify that the solution to the dataflow
2257    equations is not dirty.  */
2258
2259 static void
2260 df_live_verify_solution_start (void)
2261 {
2262   basic_block bb;
2263   struct df_live_problem_data *problem_data;
2264   if (df_live->solutions_dirty)
2265     {
2266       df_live->problem_data = NULL;
2267       return;
2268     }
2269
2270   /* Set it true so that the solution is recomputed.  */
2271   df_live->solutions_dirty = true;
2272
2273   problem_data = XNEW (struct df_live_problem_data);
2274   df_live->problem_data = problem_data;
2275   problem_data->in = XNEWVEC (bitmap, last_basic_block);
2276   problem_data->out = XNEWVEC (bitmap, last_basic_block);
2277
2278   FOR_ALL_BB (bb)
2279     {
2280       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
2281       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
2282       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
2283       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
2284     }
2285 }
2286
2287
2288 /* Compare the saved datastructure and the new solution to the dataflow
2289    equations.  */
2290
2291 static void
2292 df_live_verify_solution_end (void)
2293 {
2294   struct df_live_problem_data *problem_data;
2295   basic_block bb;
2296
2297   if (df_live->problem_data == NULL)
2298     return;
2299
2300   problem_data = (struct df_live_problem_data *)df_live->problem_data;
2301
2302   FOR_ALL_BB (bb)
2303     {
2304       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
2305           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
2306         {
2307           /*df_dump (stderr);*/
2308           gcc_unreachable ();
2309         }
2310     }
2311
2312   /* Cannot delete them immediately because you may want to dump them
2313      if the comparison fails.  */
2314   FOR_ALL_BB (bb)
2315     {
2316       BITMAP_FREE (problem_data->in[bb->index]);
2317       BITMAP_FREE (problem_data->out[bb->index]);
2318     }
2319
2320   free (problem_data->in);
2321   free (problem_data->out);
2322   free (problem_data);
2323   df_live->problem_data = NULL;
2324 }
2325
2326
2327 /* All of the information associated with every instance of the problem.  */
2328
2329 static struct df_problem problem_LIVE =
2330 {
2331   DF_LIVE,                      /* Problem id.  */
2332   DF_FORWARD,                   /* Direction.  */
2333   df_live_alloc,                /* Allocate the problem specific data.  */
2334   df_live_reset,                /* Reset global information.  */
2335   df_live_free_bb_info,         /* Free basic block info.  */
2336   df_live_local_compute,        /* Local compute function.  */
2337   df_live_init,                 /* Init the solution specific data.  */
2338   df_worklist_dataflow,         /* Worklist solver.  */
2339   NULL,                         /* Confluence operator 0.  */
2340   df_live_confluence_n,         /* Confluence operator n.  */
2341   df_live_transfer_function,    /* Transfer function.  */
2342   df_live_local_finalize,       /* Finalize function.  */
2343   df_live_free,                 /* Free all of the problem information.  */
2344   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
2345   NULL,                         /* Debugging.  */
2346   df_live_top_dump,             /* Debugging start block.  */
2347   df_live_bottom_dump,          /* Debugging end block.  */
2348   df_live_verify_solution_start,/* Incremental solution verify start.  */
2349   df_live_verify_solution_end,  /* Incremental solution verify end.  */
2350   &problem_LR,                  /* Dependent problem.  */
2351   TV_DF_LIVE,                   /* Timing variable.  */
2352   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
2353 };
2354
2355
2356 /* Create a new DATAFLOW instance and add it to an existing instance
2357    of DF.  The returned structure is what is used to get at the
2358    solution.  */
2359
2360 void
2361 df_live_add_problem (void)
2362 {
2363   df_add_problem (&problem_LIVE);
2364   /* These will be initialized when df_scan_blocks processes each
2365      block.  */
2366   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2367 }
2368
2369
2370 /* Set all of the blocks as dirty.  This needs to be done if this
2371    problem is added after all of the insns have been scanned.  */
2372
2373 void
2374 df_live_set_all_dirty (void)
2375 {
2376   basic_block bb;
2377   FOR_ALL_BB (bb)
2378     bitmap_set_bit (df_live->out_of_date_transfer_functions,
2379                     bb->index);
2380 }
2381
2382
2383 /* Verify that all of the lr related info is consistent and
2384    correct.  */
2385
2386 void
2387 df_live_verify_transfer_functions (void)
2388 {
2389   basic_block bb;
2390   bitmap saved_gen;
2391   bitmap saved_kill;
2392   bitmap all_blocks;
2393
2394   if (!df)
2395     return;
2396
2397   saved_gen = BITMAP_ALLOC (NULL);
2398   saved_kill = BITMAP_ALLOC (NULL);
2399   all_blocks = BITMAP_ALLOC (NULL);
2400
2401   df_grow_insn_info ();
2402
2403   FOR_ALL_BB (bb)
2404     {
2405       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
2406       bitmap_set_bit (all_blocks, bb->index);
2407
2408       if (bb_info)
2409         {
2410           /* Make a copy of the transfer functions and then compute
2411              new ones to see if the transfer functions have
2412              changed.  */
2413           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
2414                              bb->index))
2415             {
2416               bitmap_copy (saved_gen, bb_info->gen);
2417               bitmap_copy (saved_kill, bb_info->kill);
2418               bitmap_clear (bb_info->gen);
2419               bitmap_clear (bb_info->kill);
2420
2421               df_live_bb_local_compute (bb->index);
2422               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
2423               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
2424             }
2425         }
2426       else
2427         {
2428           /* If we do not have basic block info, the block must be in
2429              the list of dirty blocks or else some one has added a
2430              block behind our backs. */
2431           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
2432                                     bb->index));
2433         }
2434       /* Make sure no one created a block without following
2435          procedures.  */
2436       gcc_assert (df_scan_get_bb_info (bb->index));
2437     }
2438
2439   /* Make sure there are no dirty bits in blocks that have been deleted.  */
2440   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
2441                                          all_blocks));
2442   BITMAP_FREE (saved_gen);
2443   BITMAP_FREE (saved_kill);
2444   BITMAP_FREE (all_blocks);
2445 }
2446
2447
2448 \f
2449 /*----------------------------------------------------------------------------
2450    UNINITIALIZED REGISTERS WITH EARLYCLOBBER
2451
2452    Find the set of uses for registers that are reachable from the entry
2453    block without passing thru a definition.  In and out bitvectors are built
2454    for each basic block.  The regnum is used to index into these sets.
2455    See df.h for details.
2456
2457    This is a variant of the UR problem above that has a lot of special
2458    features just for the register allocation phase.  This problem
2459    should go away if someone would fix the interference graph.
2460
2461    ----------------------------------------------------------------------------*/
2462
2463 /* Private data used to compute the solution for this problem.  These
2464    data structures are not accessible outside of this module.  */
2465 struct df_urec_problem_data
2466 {
2467   bool earlyclobbers_found;     /* True if any instruction contains an
2468                                    earlyclobber.  */
2469 #ifdef STACK_REGS
2470   bitmap stack_regs;            /* Registers that may be allocated to a STACK_REGS.  */
2471 #endif
2472 };
2473
2474
2475 /* Set basic block info.  */
2476
2477 static void
2478 df_urec_set_bb_info (unsigned int index,
2479                      struct df_urec_bb_info *bb_info)
2480 {
2481   gcc_assert (df_urec);
2482   gcc_assert (index < df_urec->block_info_size);
2483   df_urec->block_info[index] = bb_info;
2484 }
2485
2486
2487 /* Free basic block info.  */
2488
2489 static void
2490 df_urec_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2491                       void *vbb_info)
2492 {
2493   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
2494   if (bb_info)
2495     {
2496       BITMAP_FREE (bb_info->gen);
2497       BITMAP_FREE (bb_info->kill);
2498       BITMAP_FREE (bb_info->in);
2499       BITMAP_FREE (bb_info->out);
2500       BITMAP_FREE (bb_info->earlyclobber);
2501       pool_free (df_urec->block_pool, bb_info);
2502     }
2503 }
2504
2505
2506 /* Allocate or reset bitmaps for DF_UREC blocks. The solution bits are
2507    not touched unless the block is new.  */
2508
2509 static void
2510 df_urec_alloc (bitmap all_blocks)
2511
2512 {
2513   unsigned int bb_index;
2514   bitmap_iterator bi;
2515   struct df_urec_problem_data *problem_data
2516     = (struct df_urec_problem_data *) df_urec->problem_data;
2517
2518   if (!df_urec->block_pool)
2519     df_urec->block_pool = create_alloc_pool ("df_urec_block pool",
2520                                            sizeof (struct df_urec_bb_info), 50);
2521
2522   if (!df_urec->problem_data)
2523     {
2524       problem_data = XNEW (struct df_urec_problem_data);
2525       df_urec->problem_data = problem_data;
2526     }
2527   problem_data->earlyclobbers_found = false;
2528
2529   df_grow_bb_info (df_urec);
2530
2531   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2532     {
2533       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2534       if (bb_info)
2535         {
2536           bitmap_clear (bb_info->kill);
2537           bitmap_clear (bb_info->gen);
2538           bitmap_clear (bb_info->earlyclobber);
2539         }
2540       else
2541         {
2542           bb_info = (struct df_urec_bb_info *) pool_alloc (df_urec->block_pool);
2543           df_urec_set_bb_info (bb_index, bb_info);
2544           bb_info->kill = BITMAP_ALLOC (NULL);
2545           bb_info->gen = BITMAP_ALLOC (NULL);
2546           bb_info->in = BITMAP_ALLOC (NULL);
2547           bb_info->out = BITMAP_ALLOC (NULL);
2548           bb_info->top = BITMAP_ALLOC (NULL);
2549           bb_info->earlyclobber = BITMAP_ALLOC (NULL);
2550         }
2551     }
2552   df_urec->optional_p = true;
2553 }
2554
2555
2556 /* The function modifies local info for register REG being changed in
2557    SETTER.  DATA is used to pass the current basic block info.  */
2558
2559 static void
2560 df_urec_mark_reg_change (rtx reg, const_rtx setter, void *data)
2561 {
2562   int regno;
2563   int endregno;
2564   int i;
2565   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2566
2567   if (GET_CODE (reg) == SUBREG)
2568     reg = SUBREG_REG (reg);
2569
2570   if (!REG_P (reg))
2571     return;
2572
2573   regno = REGNO (reg);
2574   if (regno < FIRST_PSEUDO_REGISTER)
2575     {
2576       endregno = END_HARD_REGNO (reg);
2577       for (i = regno; i < endregno; i++)
2578         {
2579           bitmap_set_bit (bb_info->kill, i);
2580
2581           if (GET_CODE (setter) != CLOBBER)
2582             bitmap_set_bit (bb_info->gen, i);
2583           else
2584             bitmap_clear_bit (bb_info->gen, i);
2585         }
2586     }
2587   else
2588     {
2589       bitmap_set_bit (bb_info->kill, regno);
2590
2591       if (GET_CODE (setter) != CLOBBER)
2592         bitmap_set_bit (bb_info->gen, regno);
2593       else
2594         bitmap_clear_bit (bb_info->gen, regno);
2595     }
2596 }
2597 /* Classes of registers which could be early clobbered in the current
2598    insn.  */
2599
2600 static VEC(int,heap) *earlyclobber_regclass;
2601
2602 /* This function finds and stores register classes that could be early
2603    clobbered in INSN.  If any earlyclobber classes are found, the function
2604    returns TRUE, in all other cases it returns FALSE.  */
2605
2606 static bool
2607 df_urec_check_earlyclobber (rtx insn)
2608 {
2609   int opno;
2610   bool found = false;
2611
2612   extract_insn (insn);
2613
2614   VEC_truncate (int, earlyclobber_regclass, 0);
2615   for (opno = 0; opno < recog_data.n_operands; opno++)
2616     {
2617       char c;
2618       bool amp_p;
2619       int i;
2620       enum reg_class class;
2621       const char *p = recog_data.constraints[opno];
2622
2623       class = NO_REGS;
2624       amp_p = false;
2625       for (;;)
2626         {
2627           c = *p;
2628           switch (c)
2629             {
2630             case '=':  case '+':  case '?':
2631             case '#':  case '!':
2632             case '*':  case '%':
2633             case 'm':  case '<':  case '>':  case 'V':  case 'o':
2634             case 'E':  case 'F':  case 'G':  case 'H':
2635             case 's':  case 'i':  case 'n':
2636             case 'I':  case 'J':  case 'K':  case 'L':
2637             case 'M':  case 'N':  case 'O':  case 'P':
2638             case 'X':
2639             case '0': case '1':  case '2':  case '3':  case '4':
2640             case '5': case '6':  case '7':  case '8':  case '9':
2641               /* These don't say anything we care about.  */
2642               break;
2643
2644             case '&':
2645               amp_p = true;
2646               break;
2647             case '\0':
2648             case ',':
2649               if (amp_p && class != NO_REGS)
2650                 {
2651                   int rc;
2652
2653                   found = true;
2654                   for (i = 0;
2655                        VEC_iterate (int, earlyclobber_regclass, i, rc);
2656                        i++)
2657                     {
2658                       if (rc == (int) class)
2659                         goto found_rc;
2660                     }
2661
2662                   /* We use VEC_quick_push here because
2663                      earlyclobber_regclass holds no more than
2664                      N_REG_CLASSES elements. */
2665                   VEC_quick_push (int, earlyclobber_regclass, (int) class);
2666                 found_rc:
2667                   ;
2668                 }
2669
2670               amp_p = false;
2671               class = NO_REGS;
2672               break;
2673
2674             case 'r':
2675               class = GENERAL_REGS;
2676               break;
2677
2678             default:
2679               class = REG_CLASS_FROM_CONSTRAINT (c, p);
2680               break;
2681             }
2682           if (c == '\0')
2683             break;
2684           p += CONSTRAINT_LEN (c, p);
2685         }
2686     }
2687
2688   return found;
2689 }
2690
2691 /* The function checks that pseudo-register *X has a class
2692    intersecting with the class of pseudo-register could be early
2693    clobbered in the same insn.
2694
2695    This function is a no-op if earlyclobber_regclass is empty.
2696
2697    Reload can assign the same hard register to uninitialized
2698    pseudo-register and early clobbered pseudo-register in an insn if
2699    the pseudo-register is used first time in given BB and not lived at
2700    the BB start.  To prevent this we don't change life information for
2701    such pseudo-registers.  */
2702
2703 static int
2704 df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
2705 {
2706   enum reg_class pref_class, alt_class;
2707   int i, regno;
2708   struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2709
2710   if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
2711     {
2712       int rc;
2713
2714       regno = REGNO (*x);
2715       if (bitmap_bit_p (bb_info->kill, regno)
2716           || bitmap_bit_p (bb_info->gen, regno))
2717         return 0;
2718       pref_class = reg_preferred_class (regno);
2719       alt_class = reg_alternate_class (regno);
2720       for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
2721         {
2722           if (reg_classes_intersect_p (rc, pref_class)
2723               || (rc != NO_REGS
2724                   && reg_classes_intersect_p (rc, alt_class)))
2725             {
2726               bitmap_set_bit (bb_info->earlyclobber, regno);
2727               break;
2728             }
2729         }
2730     }
2731   return 0;
2732 }
2733
2734 /* The function processes all pseudo-registers in *X with the aid of
2735    previous function.  */
2736
2737 static void
2738 df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
2739 {
2740   for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
2741 }
2742
2743
2744 /* Compute local uninitialized register info for basic block BB.  */
2745
2746 static void
2747 df_urec_bb_local_compute (unsigned int bb_index)
2748 {
2749   basic_block bb = BASIC_BLOCK (bb_index);
2750   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2751   rtx insn;
2752   struct df_ref **def_rec;
2753
2754   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2755     {
2756       struct df_ref *def = *def_rec;
2757       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2758         {
2759           unsigned int regno = DF_REF_REGNO (def);
2760           bitmap_set_bit (bb_info->gen, regno);
2761         }
2762     }
2763
2764   FOR_BB_INSNS (bb, insn)
2765     {
2766       if (INSN_P (insn))
2767         {
2768           note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
2769           if (df_urec_check_earlyclobber (insn))
2770             {
2771               struct df_urec_problem_data *problem_data
2772                 = (struct df_urec_problem_data *) df_urec->problem_data;
2773               problem_data->earlyclobbers_found = true;
2774               note_uses (&PATTERN (insn),
2775                          df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
2776             }
2777         }
2778     }
2779
2780   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2781     {
2782       struct df_ref *def = *def_rec;
2783       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2784         {
2785           unsigned int regno = DF_REF_REGNO (def);
2786           bitmap_set_bit (bb_info->gen, regno);
2787         }
2788     }
2789 }
2790
2791
2792 /* Compute local uninitialized register info.  */
2793
2794 static void
2795 df_urec_local_compute (bitmap all_blocks)
2796 {
2797   unsigned int bb_index;
2798   bitmap_iterator bi;
2799 #ifdef STACK_REGS
2800   int i;
2801   HARD_REG_SET stack_hard_regs, used;
2802   struct df_urec_problem_data *problem_data
2803     = (struct df_urec_problem_data *) df_urec->problem_data;
2804
2805   /* Any register that MAY be allocated to a register stack (like the
2806      387) is treated poorly.  Each such register is marked as being
2807      live everywhere.  This keeps the register allocator and the
2808      subsequent passes from doing anything useful with these values.
2809
2810      FIXME: This seems like an incredibly poor idea.  */
2811
2812   CLEAR_HARD_REG_SET (stack_hard_regs);
2813   for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
2814     SET_HARD_REG_BIT (stack_hard_regs, i);
2815   problem_data->stack_regs = BITMAP_ALLOC (NULL);
2816   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2817     {
2818       COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
2819       IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
2820       AND_HARD_REG_SET (used, stack_hard_regs);
2821       if (!hard_reg_set_empty_p (used))
2822         bitmap_set_bit (problem_data->stack_regs, i);
2823     }
2824 #endif
2825
2826   /* We know that earlyclobber_regclass holds no more than
2827     N_REG_CLASSES elements.  See df_urec_check_earlyclobber.  */
2828   earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
2829
2830   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2831     {
2832       df_urec_bb_local_compute (bb_index);
2833     }
2834
2835   VEC_free (int, heap, earlyclobber_regclass);
2836 }
2837
2838
2839 /* Initialize the solution vectors.  */
2840
2841 static void
2842 df_urec_init (bitmap all_blocks)
2843 {
2844   unsigned int bb_index;
2845   bitmap_iterator bi;
2846
2847   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2848     {
2849       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2850
2851       bitmap_copy (bb_info->out, bb_info->gen);
2852       bitmap_clear (bb_info->in);
2853     }
2854 }
2855
2856
2857 /* Or in the stack regs, hard regs and early clobber regs into the
2858    urec_in sets of all of the blocks.  */
2859
2860
2861 static void
2862 df_urec_local_finalize (bitmap all_blocks)
2863 {
2864   bitmap tmp = BITMAP_ALLOC (NULL);
2865   bitmap_iterator bi;
2866   unsigned int bb_index;
2867   struct df_urec_problem_data *problem_data
2868     = (struct df_urec_problem_data *) df_urec->problem_data;
2869
2870   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2871     {
2872       struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2873       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
2874
2875       if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
2876         {
2877           if (problem_data->earlyclobbers_found)
2878             bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
2879
2880 #ifdef STACK_REGS
2881           /* We can not use the same stack register for uninitialized
2882              pseudo-register and another living pseudo-register
2883              because if the uninitialized pseudo-register dies,
2884              subsequent pass reg-stack will be confused (it will
2885              believe that the other register dies).  */
2886           bitmap_ior_into (bb_info->in, problem_data->stack_regs);
2887           bitmap_ior_into (bb_info->out, problem_data->stack_regs);
2888 #endif
2889         }
2890
2891       /* No register may reach a location where it is not used.  Thus
2892          we trim the rr result to the places where it is used.  */
2893       bitmap_and_into (bb_info->in, bb_lr_info->in);
2894       bitmap_and_into (bb_info->out, bb_lr_info->out);
2895       bitmap_copy (bb_info->top, bb_info->in);
2896       if (bb_lr_info->adef)
2897         bitmap_ior_into (bb_info->top, bb_lr_info->adef);
2898       bitmap_and_into (bb_info->top, bb_lr_info->top);
2899 #if 0
2900       /* Hard registers may still stick in the ur_out set, but not
2901          be in the ur_in set, if their only mention was in a call
2902          in this block.  This is because a call kills in the lr
2903          problem but does not kill in the rr problem.  To clean
2904          this up, we execute the transfer function on the lr_in
2905          set and then use that to knock bits out of ur_out.  */
2906       bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
2907                             bb_info->kill);
2908       bitmap_and_into (bb_info->out, tmp);
2909 #endif
2910     }
2911
2912 #ifdef STACK_REGS
2913   BITMAP_FREE (problem_data->stack_regs);
2914 #endif
2915   BITMAP_FREE (tmp);
2916 }
2917
2918
2919 /* Confluence function that ignores fake edges.  */
2920
2921 static void
2922 df_urec_confluence_n (edge e)
2923 {
2924   bitmap op1 = df_urec_get_bb_info (e->dest->index)->in;
2925   bitmap op2 = df_urec_get_bb_info (e->src->index)->out;
2926
2927   if (e->flags & EDGE_FAKE)
2928     return;
2929
2930   bitmap_ior_into (op1, op2);
2931 }
2932
2933
2934 /* Transfer function.  */
2935
2936 static bool
2937 df_urec_transfer_function (int bb_index)
2938 {
2939   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb_index);
2940   bitmap in = bb_info->in;
2941   bitmap out = bb_info->out;
2942   bitmap gen = bb_info->gen;
2943   bitmap kill = bb_info->kill;
2944
2945   return bitmap_ior_and_compl (out, gen, in, kill);
2946 }
2947
2948
2949 /* Free all storage associated with the problem.  */
2950
2951 static void
2952 df_urec_free (void)
2953 {
2954   if (df_urec->block_info)
2955     {
2956       unsigned int i;
2957
2958       for (i = 0; i < df_urec->block_info_size; i++)
2959         {
2960           struct df_urec_bb_info *bb_info = df_urec_get_bb_info (i);
2961           if (bb_info)
2962             {
2963               BITMAP_FREE (bb_info->gen);
2964               BITMAP_FREE (bb_info->kill);
2965               BITMAP_FREE (bb_info->in);
2966               BITMAP_FREE (bb_info->out);
2967               BITMAP_FREE (bb_info->earlyclobber);
2968               BITMAP_FREE (bb_info->top);
2969             }
2970         }
2971
2972       free_alloc_pool (df_urec->block_pool);
2973
2974       df_urec->block_info_size = 0;
2975       free (df_urec->block_info);
2976       free (df_urec->problem_data);
2977     }
2978   free (df_urec);
2979 }
2980
2981
2982 /* Debugging info at top of bb.  */
2983
2984 static void
2985 df_urec_top_dump (basic_block bb, FILE *file)
2986 {
2987   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
2988   if (!bb_info || !bb_info->in)
2989     return;
2990
2991   fprintf (file, ";; urec  in  \t");
2992   df_print_regset (file, bb_info->in);
2993   fprintf (file, ";; urec  gen \t");
2994   df_print_regset (file, bb_info->gen);
2995   fprintf (file, ";; urec  kill\t");
2996   df_print_regset (file, bb_info->kill);
2997   fprintf (file, ";; urec  ec\t");
2998   df_print_regset (file, bb_info->earlyclobber);
2999 }
3000
3001
3002 /* Debugging info at bottom of bb.  */
3003
3004 static void
3005 df_urec_bottom_dump (basic_block bb, FILE *file)
3006 {
3007   struct df_urec_bb_info *bb_info = df_urec_get_bb_info (bb->index);
3008   if (!bb_info || !bb_info->out)
3009     return;
3010   fprintf (file, ";; urec  out \t");
3011   df_print_regset (file, bb_info->out);
3012 }
3013
3014
3015 /* All of the information associated with every instance of the problem.  */
3016
3017 static struct df_problem problem_UREC =
3018 {
3019   DF_UREC,                    /* Problem id.  */
3020   DF_FORWARD,                 /* Direction.  */
3021   df_urec_alloc,              /* Allocate the problem specific data.  */
3022   NULL,                       /* Reset global information.  */
3023   df_urec_free_bb_info,       /* Free basic block info.  */
3024   df_urec_local_compute,      /* Local compute function.  */
3025   df_urec_init,               /* Init the solution specific data.  */
3026   df_worklist_dataflow,       /* Worklist solver.  */
3027   NULL,                       /* Confluence operator 0.  */
3028   df_urec_confluence_n,       /* Confluence operator n.  */
3029   df_urec_transfer_function,  /* Transfer function.  */
3030   df_urec_local_finalize,     /* Finalize function.  */
3031   df_urec_free,               /* Free all of the problem information.  */
3032   df_urec_free,               /* Remove this problem from the stack of dataflow problems.  */
3033   NULL,                       /* Debugging.  */
3034   df_urec_top_dump,           /* Debugging start block.  */
3035   df_urec_bottom_dump,        /* Debugging end block.  */
3036   NULL,                       /* Incremental solution verify start.  */
3037   NULL,                       /* Incremental solution verify end.  */
3038   &problem_LR,                /* Dependent problem.  */
3039   TV_DF_UREC,                 /* Timing variable.  */
3040   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3041 };
3042
3043
3044 /* Create a new DATAFLOW instance and add it to an existing instance
3045    of DF.  The returned structure is what is used to get at the
3046    solution.  */
3047
3048 void
3049 df_urec_add_problem (void)
3050 {
3051   df_add_problem (&problem_UREC);
3052 }
3053
3054
3055 \f
3056 /*----------------------------------------------------------------------------
3057    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
3058
3059    Link either the defs to the uses and / or the uses to the defs.
3060
3061    These problems are set up like the other dataflow problems so that
3062    they nicely fit into the framework.  They are much simpler and only
3063    involve a single traversal of instructions and an examination of
3064    the reaching defs information (the dependent problem).
3065 ----------------------------------------------------------------------------*/
3066
3067 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
3068
3069 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
3070
3071 struct df_link *
3072 df_chain_create (struct df_ref *src, struct df_ref *dst)
3073 {
3074   struct df_link *head = DF_REF_CHAIN (src);
3075   struct df_link *link = pool_alloc (df_chain->block_pool);;
3076
3077   DF_REF_CHAIN (src) = link;
3078   link->next = head;
3079   link->ref = dst;
3080   return link;
3081 }
3082
3083
3084 /* Delete any du or ud chains that start at REF and point to
3085    TARGET.  */
3086 static void
3087 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
3088 {
3089   struct df_link *chain = DF_REF_CHAIN (ref);
3090   struct df_link *prev = NULL;
3091
3092   while (chain)
3093     {
3094       if (chain->ref == target)
3095         {
3096           if (prev)
3097             prev->next = chain->next;
3098           else
3099             DF_REF_CHAIN (ref) = chain->next;
3100           pool_free (df_chain->block_pool, chain);
3101           return;
3102         }
3103       prev = chain;
3104       chain = chain->next;
3105     }
3106 }
3107
3108
3109 /* Delete a du or ud chain that leave or point to REF.  */
3110
3111 void
3112 df_chain_unlink (struct df_ref *ref)
3113 {
3114   struct df_link *chain = DF_REF_CHAIN (ref);
3115   while (chain)
3116     {
3117       struct df_link *next = chain->next;
3118       /* Delete the other side if it exists.  */
3119       df_chain_unlink_1 (chain->ref, ref);
3120       pool_free (df_chain->block_pool, chain);
3121       chain = next;
3122     }
3123   DF_REF_CHAIN (ref) = NULL;
3124 }
3125
3126
3127 /* Copy the du or ud chain starting at FROM_REF and attach it to
3128    TO_REF.  */
3129
3130 void
3131 df_chain_copy (struct df_ref *to_ref,
3132                struct df_link *from_ref)
3133 {
3134   while (from_ref)
3135     {
3136       df_chain_create (to_ref, from_ref->ref);
3137       from_ref = from_ref->next;
3138     }
3139 }
3140
3141
3142 /* Remove this problem from the stack of dataflow problems.  */
3143
3144 static void
3145 df_chain_remove_problem (void)
3146 {
3147   bitmap_iterator bi;
3148   unsigned int bb_index;
3149
3150   /* Wholesale destruction of the old chains.  */
3151   if (df_chain->block_pool)
3152     free_alloc_pool (df_chain->block_pool);
3153
3154   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
3155     {
3156       rtx insn;
3157       struct df_ref **def_rec;
3158       struct df_ref **use_rec;
3159       basic_block bb = BASIC_BLOCK (bb_index);
3160
3161       if (df_chain_problem_p (DF_DU_CHAIN))
3162         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
3163           DF_REF_CHAIN (*def_rec) = NULL;
3164       if (df_chain_problem_p (DF_UD_CHAIN))
3165         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
3166           DF_REF_CHAIN (*use_rec) = NULL;
3167
3168       FOR_BB_INSNS (bb, insn)
3169         {
3170           unsigned int uid = INSN_UID (insn);
3171
3172           if (INSN_P (insn))
3173             {
3174               if (df_chain_problem_p (DF_DU_CHAIN))
3175                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3176                   DF_REF_CHAIN (*def_rec) = NULL;
3177               if (df_chain_problem_p (DF_UD_CHAIN))
3178                 {
3179                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3180                     DF_REF_CHAIN (*use_rec) = NULL;
3181                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
3182                     DF_REF_CHAIN (*use_rec) = NULL;
3183                 }
3184             }
3185         }
3186     }
3187
3188   bitmap_clear (df_chain->out_of_date_transfer_functions);
3189   df_chain->block_pool = NULL;
3190 }
3191
3192
3193 /* Remove the chain problem completely.  */
3194
3195 static void
3196 df_chain_fully_remove_problem (void)
3197 {
3198   df_chain_remove_problem ();
3199   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3200   free (df_chain);
3201 }
3202
3203
3204 /* Create def-use or use-def chains.  */
3205
3206 static void
3207 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3208 {
3209   df_chain_remove_problem ();
3210   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
3211                                          sizeof (struct df_link), 50);
3212   df_chain->optional_p = true;
3213 }
3214
3215
3216 /* Reset all of the chains when the set of basic blocks changes.  */
3217
3218 static void
3219 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
3220 {
3221   df_chain_remove_problem ();
3222 }
3223
3224
3225 /* Create the chains for a list of USEs.  */
3226
3227 static void
3228 df_chain_create_bb_process_use (bitmap local_rd,
3229                                 struct df_ref **use_rec,
3230                                 enum df_ref_flags top_flag)
3231 {
3232   bitmap_iterator bi;
3233   unsigned int def_index;
3234
3235   while (*use_rec)
3236     {
3237       struct df_ref *use = *use_rec;
3238       unsigned int uregno = DF_REF_REGNO (use);
3239       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3240           || (uregno >= FIRST_PSEUDO_REGISTER))
3241         {
3242           /* Do not want to go through this for an uninitialized var.  */
3243           int count = DF_DEFS_COUNT (uregno);
3244           if (count)
3245             {
3246               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
3247                 {
3248                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
3249                   unsigned int last_index = first_index + count - 1;
3250
3251                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
3252                     {
3253                       struct df_ref *def;
3254                       if (def_index > last_index)
3255                         break;
3256
3257                       def = DF_DEFS_GET (def_index);
3258                       if (df_chain_problem_p (DF_DU_CHAIN))
3259                         df_chain_create (def, use);
3260                       if (df_chain_problem_p (DF_UD_CHAIN))
3261                         df_chain_create (use, def);
3262                     }
3263                 }
3264             }
3265         }
3266
3267       use_rec++;
3268     }
3269 }
3270
3271
3272 /* Create chains from reaching defs bitmaps for basic block BB.  */
3273
3274 static void
3275 df_chain_create_bb (unsigned int bb_index)
3276 {
3277   basic_block bb = BASIC_BLOCK (bb_index);
3278   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
3279   rtx insn;
3280   bitmap cpy = BITMAP_ALLOC (NULL);
3281   struct df_ref **def_rec;
3282
3283   bitmap_copy (cpy, bb_info->in);
3284   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
3285
3286   /* Since we are going forwards, process the artificial uses first
3287      then the artificial defs second.  */
3288
3289 #ifdef EH_USES
3290   /* Create the chains for the artificial uses from the EH_USES at the
3291      beginning of the block.  */
3292
3293   /* Artificials are only hard regs.  */
3294   if (!(df->changeable_flags & DF_NO_HARD_REGS))
3295     df_chain_create_bb_process_use (cpy,
3296                                     df_get_artificial_uses (bb->index),
3297                                     DF_REF_AT_TOP);
3298 #endif
3299
3300   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3301     {
3302       struct df_ref *def = *def_rec;
3303       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3304         {
3305           unsigned int dregno = DF_REF_REGNO (def);
3306           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3307             bitmap_clear_range (cpy,
3308                                 DF_DEFS_BEGIN (dregno),
3309                                 DF_DEFS_COUNT (dregno));
3310           bitmap_set_bit (cpy, DF_REF_ID (def));
3311         }
3312     }
3313
3314   /* Process the regular instructions next.  */
3315   FOR_BB_INSNS (bb, insn)
3316     {
3317       struct df_ref **def_rec;
3318       unsigned int uid = INSN_UID (insn);
3319
3320       if (!INSN_P (insn))
3321         continue;
3322
3323       /* Now scan the uses and link them up with the defs that remain
3324          in the cpy vector.  */
3325
3326       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
3327
3328       if (df->changeable_flags & DF_EQ_NOTES)
3329         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
3330
3331
3332       /* Since we are going forwards, process the defs second.  This
3333          pass only changes the bits in cpy.  */
3334       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3335         {
3336           struct df_ref *def = *def_rec;
3337           unsigned int dregno = DF_REF_REGNO (def);
3338           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3339               || (dregno >= FIRST_PSEUDO_REGISTER))
3340             {
3341               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3342                 bitmap_clear_range (cpy,
3343                                     DF_DEFS_BEGIN (dregno),
3344                                     DF_DEFS_COUNT (dregno));
3345               if (!(DF_REF_FLAGS (def)
3346                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3347                 bitmap_set_bit (cpy, DF_REF_ID (def));
3348             }
3349         }
3350     }
3351
3352   /* Create the chains for the artificial uses of the hard registers
3353      at the end of the block.  */
3354   if (!(df->changeable_flags & DF_NO_HARD_REGS))
3355     df_chain_create_bb_process_use (cpy,
3356                                     df_get_artificial_uses (bb->index),
3357                                     0);
3358
3359   BITMAP_FREE (cpy);
3360 }
3361
3362 /* Create def-use chains from reaching use bitmaps for basic blocks
3363    in BLOCKS.  */
3364
3365 static void
3366 df_chain_finalize (bitmap all_blocks)
3367 {
3368   unsigned int bb_index;
3369   bitmap_iterator bi;
3370
3371   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3372     {
3373       df_chain_create_bb (bb_index);
3374     }
3375 }
3376
3377
3378 /* Free all storage associated with the problem.  */
3379
3380 static void
3381 df_chain_free (void)
3382 {
3383   free_alloc_pool (df_chain->block_pool);
3384   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
3385   free (df_chain);
3386 }
3387
3388
3389 /* Debugging info.  */
3390
3391 static void
3392 df_chain_top_dump (basic_block bb, FILE *file)
3393 {
3394   if (df_chain_problem_p (DF_DU_CHAIN))
3395     {
3396       rtx insn;
3397       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
3398       if (*def_rec)
3399         {
3400
3401           fprintf (file, ";;  DU chains for artificial defs\n");
3402           while (*def_rec)
3403             {
3404               struct df_ref *def = *def_rec;
3405               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
3406               df_chain_dump (DF_REF_CHAIN (def), file);
3407               fprintf (file, "\n");
3408               def_rec++;
3409             }
3410         }
3411
3412       FOR_BB_INSNS (bb, insn)
3413         {
3414           unsigned int uid = INSN_UID (insn);
3415           if (INSN_P (insn))
3416             {
3417               def_rec = DF_INSN_UID_DEFS (uid);
3418               if (*def_rec)
3419                 {
3420                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
3421                            DF_INSN_LUID (insn), uid);
3422
3423                   while (*def_rec)
3424                     {
3425                       struct df_ref *def = *def_rec;
3426                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
3427                       if (def->flags & DF_REF_READ_WRITE)
3428                         fprintf (file, "read/write ");
3429                       df_chain_dump (DF_REF_CHAIN (def), file);
3430                       fprintf (file, "\n");
3431                       def_rec++;
3432                     }
3433                 }
3434             }
3435         }
3436     }
3437 }
3438
3439
3440 static void
3441 df_chain_bottom_dump (basic_block bb, FILE *file)
3442 {
3443   if (df_chain_problem_p (DF_UD_CHAIN))
3444     {
3445       rtx insn;
3446       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
3447
3448       if (*use_rec)
3449         {
3450           fprintf (file, ";;  UD chains for artificial uses\n");
3451           while (*use_rec)
3452             {
3453               struct df_ref *use = *use_rec;
3454               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
3455               df_chain_dump (DF_REF_CHAIN (use), file);
3456               fprintf (file, "\n");
3457               use_rec++;
3458             }
3459         }
3460
3461       FOR_BB_INSNS (bb, insn)
3462         {
3463           unsigned int uid = INSN_UID (insn);
3464           if (INSN_P (insn))
3465             {
3466               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
3467               use_rec = DF_INSN_UID_USES (uid);
3468               if (*use_rec || *eq_use_rec)
3469                 {
3470                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
3471                            DF_INSN_LUID (insn), uid);
3472
3473                   while (*use_rec)
3474                     {
3475                       struct df_ref *use = *use_rec;
3476                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
3477                       if (use->flags & DF_REF_READ_WRITE)
3478                         fprintf (file, "read/write ");
3479                       df_chain_dump (DF_REF_CHAIN (use), file);
3480                       fprintf (file, "\n");
3481                       use_rec++;
3482                     }
3483                   while (*eq_use_rec)
3484                     {
3485                       struct df_ref *use = *eq_use_rec;
3486                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
3487                       df_chain_dump (DF_REF_CHAIN (use), file);
3488                       fprintf (file, "\n");
3489                       eq_use_rec++;
3490                     }
3491                 }
3492             }
3493         }
3494     }
3495 }
3496
3497
3498 static struct df_problem problem_CHAIN =
3499 {
3500   DF_CHAIN,                   /* Problem id.  */
3501   DF_NONE,                    /* Direction.  */
3502   df_chain_alloc,             /* Allocate the problem specific data.  */
3503   df_chain_reset,             /* Reset global information.  */
3504   NULL,                       /* Free basic block info.  */
3505   NULL,                       /* Local compute function.  */
3506   NULL,                       /* Init the solution specific data.  */
3507   NULL,                       /* Iterative solver.  */
3508   NULL,                       /* Confluence operator 0.  */
3509   NULL,                       /* Confluence operator n.  */
3510   NULL,                       /* Transfer function.  */
3511   df_chain_finalize,          /* Finalize function.  */
3512   df_chain_free,              /* Free all of the problem information.  */
3513   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
3514   NULL,                       /* Debugging.  */
3515   df_chain_top_dump,          /* Debugging start block.  */
3516   df_chain_bottom_dump,       /* Debugging end block.  */
3517   NULL,                       /* Incremental solution verify start.  */
3518   NULL,                       /* Incremental solution verify end.  */
3519   &problem_RD,                /* Dependent problem.  */
3520   TV_DF_CHAIN,                /* Timing variable.  */
3521   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3522 };
3523
3524
3525 /* Create a new DATAFLOW instance and add it to an existing instance
3526    of DF.  The returned structure is what is used to get at the
3527    solution.  */
3528
3529 void
3530 df_chain_add_problem (enum df_chain_flags chain_flags)
3531 {
3532   df_add_problem (&problem_CHAIN);
3533   df_chain->local_flags = (unsigned int)chain_flags;
3534   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
3535 }
3536
3537 #undef df_chain_problem_p
3538
3539 \f
3540 /*----------------------------------------------------------------------------
3541    This pass computes REG_DEAD and REG_UNUSED notes.
3542    ----------------------------------------------------------------------------*/
3543
3544 static void
3545 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3546 {
3547   df_note->optional_p = true;
3548 }
3549
3550 #ifdef REG_DEAD_DEBUGGING
3551 static void
3552 df_print_note (const char *prefix, rtx insn, rtx note)
3553 {
3554   if (dump_file)
3555     {
3556       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3557       print_rtl (dump_file, note);
3558       fprintf (dump_file, "\n");
3559     }
3560 }
3561 #endif
3562
3563
3564 /* After reg-stack, the x86 floating point stack regs are difficult to
3565    analyze because of all of the pushes, pops and rotations.  Thus, we
3566    just leave the notes alone. */
3567
3568 #ifdef STACK_REGS
3569 static inline bool
3570 df_ignore_stack_reg (int regno)
3571 {
3572   return regstack_completed
3573     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3574 }
3575 #else
3576 static inline bool
3577 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3578 {
3579   return false;
3580 }
3581 #endif
3582
3583
3584 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3585    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
3586
3587 static void
3588 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3589 {
3590   rtx *pprev = &REG_NOTES (insn);
3591   rtx link = *pprev;
3592   rtx dead = NULL;
3593   rtx unused = NULL;
3594
3595   while (link)
3596     {
3597       switch (REG_NOTE_KIND (link))
3598         {
3599         case REG_DEAD:
3600           /* After reg-stack, we need to ignore any unused notes
3601              for the stack registers.  */
3602           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3603             {
3604               pprev = &XEXP (link, 1);
3605               link = *pprev;
3606             }
3607           else
3608             {
3609               rtx next = XEXP (link, 1);
3610 #ifdef REG_DEAD_DEBUGGING
3611               df_print_note ("deleting: ", insn, link);
3612 #endif
3613               XEXP (link, 1) = dead;
3614               dead = link;
3615               *pprev = link = next;
3616             }
3617           break;
3618
3619         case REG_UNUSED:
3620           /* After reg-stack, we need to ignore any unused notes
3621              for the stack registers.  */
3622           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3623             {
3624               pprev = &XEXP (link, 1);
3625               link = *pprev;
3626             }
3627           else
3628             {
3629               rtx next = XEXP (link, 1);
3630 #ifdef REG_DEAD_DEBUGGING
3631               df_print_note ("deleting: ", insn, link);
3632 #endif
3633               XEXP (link, 1) = unused;
3634               unused = link;
3635               *pprev = link = next;
3636             }
3637           break;
3638
3639         default:
3640           pprev = &XEXP (link, 1);
3641           link = *pprev;
3642           break;
3643         }
3644     }
3645
3646   *old_dead_notes = dead;
3647   *old_unused_notes = unused;
3648 }
3649
3650
3651 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
3652    list, otherwise create a new one.  */
3653
3654 static inline rtx
3655 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3656 {
3657   rtx this = old;
3658   rtx prev = NULL;
3659
3660   while (this)
3661     if (XEXP (this, 0) == reg)
3662       {
3663         if (prev)
3664           XEXP (prev, 1) = XEXP (this, 1);
3665         else
3666           old = XEXP (this, 1);
3667         XEXP (this, 1) = REG_NOTES (insn);
3668         REG_NOTES (insn) = this;
3669         return old;
3670       }
3671     else
3672       {
3673         prev = this;
3674         this = XEXP (this, 1);
3675       }
3676
3677   /* Did not find the note.  */
3678   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3679   return old;
3680 }
3681
3682 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3683    arguments.  Return true if the register value described by MWS's
3684    mw_reg is known to be completely unused, and if mw_reg can therefore
3685    be used in a REG_UNUSED note.  */
3686
3687 static bool
3688 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3689                           bitmap live, bitmap artificial_uses)
3690 {
3691   unsigned int r;
3692
3693   /* If MWS describes a partial reference, create REG_UNUSED notes for
3694      individual hard registers.  */
3695   if (mws->flags & DF_REF_PARTIAL)
3696     return false;
3697
3698   /* Likewise if some part of the register is used.  */
3699   for (r = mws->start_regno; r <= mws->end_regno; r++)
3700     if (bitmap_bit_p (live, r)
3701         || bitmap_bit_p (artificial_uses, r))
3702       return false;
3703
3704   gcc_assert (REG_P (mws->mw_reg));
3705   return true;
3706 }
3707
3708 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3709    based on the bits in LIVE.  Do not generate notes for registers in
3710    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
3711    not generated if the reg is both read and written by the
3712    instruction.
3713 */
3714
3715 static rtx
3716 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3717                             bitmap live, bitmap do_not_gen,
3718                             bitmap artificial_uses)
3719 {
3720   unsigned int r;
3721
3722 #ifdef REG_DEAD_DEBUGGING
3723   if (dump_file)
3724     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3725              mws->start_regno, mws->end_regno);
3726 #endif
3727
3728   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3729     {
3730       unsigned int regno = mws->start_regno;
3731       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3732
3733 #ifdef REG_DEAD_DEBUGGING
3734       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3735 #endif
3736       bitmap_set_bit (do_not_gen, regno);
3737       /* Only do this if the value is totally dead.  */
3738     }
3739   else
3740     for (r = mws->start_regno; r <= mws->end_regno; r++)
3741       {
3742         if (!bitmap_bit_p (live, r)
3743             && !bitmap_bit_p (artificial_uses, r))
3744           {
3745             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3746 #ifdef REG_DEAD_DEBUGGING
3747             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3748 #endif
3749           }
3750         bitmap_set_bit (do_not_gen, r);
3751       }
3752   return old;
3753 }
3754
3755
3756 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3757    arguments.  Return true if the register value described by MWS's
3758    mw_reg is known to be completely dead, and if mw_reg can therefore
3759    be used in a REG_DEAD note.  */
3760
3761 static bool
3762 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3763                         bitmap live, bitmap artificial_uses,
3764                         bitmap do_not_gen)
3765 {
3766   unsigned int r;
3767
3768   /* If MWS describes a partial reference, create REG_DEAD notes for
3769      individual hard registers.  */
3770   if (mws->flags & DF_REF_PARTIAL)
3771     return false;
3772
3773   /* Likewise if some part of the register is not dead.  */
3774   for (r = mws->start_regno; r <= mws->end_regno; r++)
3775     if (bitmap_bit_p (live, r)
3776         || bitmap_bit_p (artificial_uses, r)
3777         || bitmap_bit_p (do_not_gen, r))
3778       return false;
3779
3780   gcc_assert (REG_P (mws->mw_reg));
3781   return true;
3782 }
3783
3784 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3785    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
3786    from being set if the instruction both reads and writes the
3787    register.  */
3788
3789 static rtx
3790 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3791                           bitmap live, bitmap do_not_gen,
3792                           bitmap artificial_uses)
3793 {
3794   unsigned int r;
3795
3796 #ifdef REG_DEAD_DEBUGGING
3797   if (dump_file)
3798     {
3799       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
3800                mws->start_regno, mws->end_regno);
3801       df_print_regset (dump_file, do_not_gen);
3802       fprintf (dump_file, "  live =");
3803       df_print_regset (dump_file, live);
3804       fprintf (dump_file, "  artificial uses =");
3805       df_print_regset (dump_file, artificial_uses);
3806     }
3807 #endif
3808
3809   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3810     {
3811       /* Add a dead note for the entire multi word register.  */
3812       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3813 #ifdef REG_DEAD_DEBUGGING
3814       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3815 #endif
3816     }
3817   else
3818     {
3819       for (r = mws->start_regno; r <= mws->end_regno; r++)
3820         if (!bitmap_bit_p (live, r)
3821             && !bitmap_bit_p (artificial_uses, r)
3822             && !bitmap_bit_p (do_not_gen, r))
3823           {
3824             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3825 #ifdef REG_DEAD_DEBUGGING
3826             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3827 #endif
3828           }
3829     }
3830   return old;
3831 }
3832
3833
3834 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3835    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3836
3837 static rtx
3838 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3839                        bitmap live, bitmap artificial_uses)
3840 {
3841   unsigned int dregno = DF_REF_REGNO (def);
3842
3843 #ifdef REG_DEAD_DEBUGGING
3844   if (dump_file)
3845     {
3846       fprintf (dump_file, "  regular looking at def ");
3847       df_ref_debug (def, dump_file);
3848     }
3849 #endif
3850
3851   if (!(bitmap_bit_p (live, dregno)
3852         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3853         || bitmap_bit_p (artificial_uses, dregno)
3854         || df_ignore_stack_reg (dregno)))
3855     {
3856       rtx reg = (DF_REF_LOC (def))
3857                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3858       old = df_set_note (REG_UNUSED, insn, old, reg);
3859 #ifdef REG_DEAD_DEBUGGING
3860       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3861 #endif
3862     }
3863
3864   return old;
3865 }
3866
3867
3868 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3869    info: lifetime, bb, and number of defs and uses for basic block
3870    BB.  The three bitvectors are scratch regs used here.  */
3871
3872 static void
3873 df_note_bb_compute (unsigned int bb_index,
3874                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3875 {
3876   basic_block bb = BASIC_BLOCK (bb_index);
3877   rtx insn;
3878   struct df_ref **def_rec;
3879   struct df_ref **use_rec;
3880
3881   bitmap_copy (live, df_get_live_out (bb));
3882   bitmap_clear (artificial_uses);
3883
3884 #ifdef REG_DEAD_DEBUGGING
3885   if (dump_file)
3886     {
3887       fprintf (dump_file, "live at bottom ");
3888       df_print_regset (dump_file, live);
3889     }
3890 #endif
3891
3892   /* Process the artificial defs and uses at the bottom of the block
3893      to begin processing.  */
3894   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3895     {
3896       struct df_ref *def = *def_rec;
3897 #ifdef REG_DEAD_DEBUGGING
3898       if (dump_file)
3899         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3900 #endif
3901
3902       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3903         bitmap_clear_bit (live, DF_REF_REGNO (def));
3904     }
3905
3906   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3907     {
3908       struct df_ref *use = *use_rec;
3909       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3910         {
3911           unsigned int regno = DF_REF_REGNO (use);
3912           bitmap_set_bit (live, regno);
3913
3914           /* Notes are not generated for any of the artificial registers
3915              at the bottom of the block.  */
3916           bitmap_set_bit (artificial_uses, regno);
3917         }
3918     }
3919
3920 #ifdef REG_DEAD_DEBUGGING
3921   if (dump_file)
3922     {
3923       fprintf (dump_file, "live before artificials out ");
3924       df_print_regset (dump_file, live);
3925     }
3926 #endif
3927
3928   FOR_BB_INSNS_REVERSE (bb, insn)
3929     {
3930       unsigned int uid = INSN_UID (insn);
3931       struct df_mw_hardreg **mws_rec;
3932       rtx old_dead_notes;
3933       rtx old_unused_notes;
3934
3935       if (!INSN_P (insn))
3936         continue;
3937
3938       bitmap_clear (do_not_gen);
3939       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3940
3941       /* Process the defs.  */
3942       if (CALL_P (insn))
3943         {
3944 #ifdef REG_DEAD_DEBUGGING
3945           if (dump_file)
3946             {
3947               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3948               df_print_regset (dump_file, live);
3949             }
3950 #endif
3951           /* We only care about real sets for calls.  Clobbers cannot
3952              be depended on to really die.  */
3953           mws_rec = DF_INSN_UID_MWS (uid);
3954           while (*mws_rec)
3955             {
3956               struct df_mw_hardreg *mws = *mws_rec;
3957               if ((mws->type == DF_REF_REG_DEF)
3958                   && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
3959                 old_unused_notes
3960                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3961                                                 mws, live, do_not_gen,
3962                                                 artificial_uses);
3963               mws_rec++;
3964             }
3965
3966           /* All of the defs except the return value are some sort of
3967              clobber.  This code is for the return.  */
3968           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3969             {
3970               struct df_ref *def = *def_rec;
3971               unsigned int dregno = DF_REF_REGNO (def);
3972               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3973                 {
3974                   old_unused_notes
3975                     = df_create_unused_note (insn, old_unused_notes,
3976                                              def, live, artificial_uses);
3977                   bitmap_set_bit (do_not_gen, dregno);
3978                 }
3979
3980               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3981                 bitmap_clear_bit (live, dregno);
3982             }
3983         }
3984       else
3985         {
3986           /* Regular insn.  */
3987           mws_rec = DF_INSN_UID_MWS (uid);
3988           while (*mws_rec)
3989             {
3990               struct df_mw_hardreg *mws = *mws_rec;
3991               if (mws->type == DF_REF_REG_DEF)
3992                 old_unused_notes
3993                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
3994                                                 mws, live, do_not_gen,
3995                                                 artificial_uses);
3996               mws_rec++;
3997             }
3998
3999           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4000             {
4001               struct df_ref *def = *def_rec;
4002               unsigned int dregno = DF_REF_REGNO (def);
4003               old_unused_notes
4004                 = df_create_unused_note (insn, old_unused_notes,
4005                                          def, live, artificial_uses);
4006
4007               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
4008                 bitmap_set_bit (do_not_gen, dregno);
4009
4010               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
4011                 bitmap_clear_bit (live, dregno);
4012             }
4013         }
4014
4015       /* Process the uses.  */
4016       mws_rec = DF_INSN_UID_MWS (uid);
4017       while (*mws_rec)
4018         {
4019           struct df_mw_hardreg *mws = *mws_rec;
4020           if ((mws->type != DF_REF_REG_DEF)
4021               && !df_ignore_stack_reg (REGNO (mws->mw_reg)))
4022             old_dead_notes
4023               = df_set_dead_notes_for_mw (insn, old_dead_notes,
4024                                           mws, live, do_not_gen,
4025                                           artificial_uses);
4026           mws_rec++;
4027         }
4028
4029       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
4030         {
4031           struct df_ref *use = *use_rec;
4032           unsigned int uregno = DF_REF_REGNO (use);
4033
4034 #ifdef REG_DEAD_DEBUGGING
4035           if (dump_file)
4036             {
4037               fprintf (dump_file, "  regular looking at use ");
4038               df_ref_debug (use, dump_file);
4039             }
4040 #endif
4041           if (!bitmap_bit_p (live, uregno))
4042             {
4043               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
4044                    && (!bitmap_bit_p (do_not_gen, uregno))
4045                    && (!bitmap_bit_p (artificial_uses, uregno))
4046                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
4047                    && (!df_ignore_stack_reg (uregno)))
4048                 {
4049                   rtx reg = (DF_REF_LOC (use))
4050                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
4051                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
4052
4053 #ifdef REG_DEAD_DEBUGGING
4054                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
4055 #endif
4056                 }
4057               /* This register is now live.  */
4058               bitmap_set_bit (live, uregno);
4059             }
4060         }
4061
4062       while (old_unused_notes)
4063         {
4064           rtx next = XEXP (old_unused_notes, 1);
4065           free_EXPR_LIST_node (old_unused_notes);
4066           old_unused_notes = next;
4067         }
4068       while (old_dead_notes)
4069         {
4070           rtx next = XEXP (old_dead_notes, 1);
4071           free_EXPR_LIST_node (old_dead_notes);
4072           old_dead_notes = next;
4073         }
4074     }
4075 }
4076
4077
4078 /* Compute register info: lifetime, bb, and number of defs and uses.  */
4079 static void
4080 df_note_compute (bitmap all_blocks)
4081 {
4082   unsigned int bb_index;
4083   bitmap_iterator bi;
4084   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
4085   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
4086   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4087
4088 #ifdef REG_DEAD_DEBUGGING
4089   if (dump_file)
4090     print_rtl_with_bb (dump_file, get_insns());
4091 #endif
4092
4093   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4094   {
4095     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
4096   }
4097
4098   BITMAP_FREE (live);
4099   BITMAP_FREE (do_not_gen);
4100   BITMAP_FREE (artificial_uses);
4101 }
4102
4103
4104 /* Free all storage associated with the problem.  */
4105
4106 static void
4107 df_note_free (void)
4108 {
4109   free (df_note);
4110 }
4111
4112
4113 /* All of the information associated every instance of the problem.  */
4114
4115 static struct df_problem problem_NOTE =
4116 {
4117   DF_NOTE,                    /* Problem id.  */
4118   DF_NONE,                    /* Direction.  */
4119   df_note_alloc,              /* Allocate the problem specific data.  */
4120   NULL,                       /* Reset global information.  */
4121   NULL,                       /* Free basic block info.  */
4122   df_note_compute,            /* Local compute function.  */
4123   NULL,                       /* Init the solution specific data.  */
4124   NULL,                       /* Iterative solver.  */
4125   NULL,                       /* Confluence operator 0.  */
4126   NULL,                       /* Confluence operator n.  */
4127   NULL,                       /* Transfer function.  */
4128   NULL,                       /* Finalize function.  */
4129   df_note_free,               /* Free all of the problem information.  */
4130   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
4131   NULL,                       /* Debugging.  */
4132   NULL,                       /* Debugging start block.  */
4133   NULL,                       /* Debugging end block.  */
4134   NULL,                       /* Incremental solution verify start.  */
4135   NULL,                       /* Incremental solution verify end.  */
4136
4137   /* Technically this is only dependent on the live registers problem
4138      but it will produce information if built one of uninitialized
4139      register problems (UR, UREC) is also run.  */
4140   &problem_LR,                /* Dependent problem.  */
4141   TV_DF_NOTE,                 /* Timing variable.  */
4142   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4143 };
4144
4145
4146 /* Create a new DATAFLOW instance and add it to an existing instance
4147    of DF.  The returned structure is what is used to get at the
4148    solution.  */
4149
4150 void
4151 df_note_add_problem (void)
4152 {
4153   df_add_problem (&problem_NOTE);
4154 }
4155
4156
4157
4158 \f
4159 /*----------------------------------------------------------------------------
4160    Functions for simulating the effects of single insns.
4161
4162    You can either simulate in the forwards direction, starting from
4163    the top of a block or the backwards direction from the end of the
4164    block.  The main difference is that if you go forwards, the uses
4165    are examined first then the defs, and if you go backwards, the defs
4166    are examined first then the uses.
4167
4168    If you start at the top of the block, use one of DF_LIVE_IN or
4169    DF_LR_IN.  If you start at the bottom of the block use one of
4170    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
4171    THEY WILL BE DESTROYED.
4172
4173 ----------------------------------------------------------------------------*/
4174
4175
4176 /* Find the set of DEFs for INSN.  */
4177
4178 void
4179 df_simulate_find_defs (rtx insn, bitmap defs)
4180 {
4181   struct df_ref **def_rec;
4182   unsigned int uid = INSN_UID (insn);
4183
4184   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4185     {
4186       struct df_ref *def = *def_rec;
4187       /* If the def is to only part of the reg, it does
4188          not kill the other defs that reach here.  */
4189       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4190         bitmap_set_bit (defs, DF_REF_REGNO (def));
4191     }
4192 }
4193
4194
4195 /* Simulate the effects of the defs of INSN on LIVE.  */
4196
4197 void
4198 df_simulate_defs (rtx insn, bitmap live)
4199 {
4200   struct df_ref **def_rec;
4201   unsigned int uid = INSN_UID (insn);
4202
4203   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4204     {
4205       struct df_ref *def = *def_rec;
4206       unsigned int dregno = DF_REF_REGNO (def);
4207
4208       /* If the def is to only part of the reg, it does
4209          not kill the other defs that reach here.  */
4210       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
4211         bitmap_clear_bit (live, dregno);
4212     }
4213 }
4214
4215
4216 /* Simulate the effects of the uses of INSN on LIVE.  */
4217
4218 void
4219 df_simulate_uses (rtx insn, bitmap live)
4220 {
4221   struct df_ref **use_rec;
4222   unsigned int uid = INSN_UID (insn);
4223
4224   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
4225     {
4226       struct df_ref *use = *use_rec;
4227       /* Add use to set of uses in this BB.  */
4228       bitmap_set_bit (live, DF_REF_REGNO (use));
4229     }
4230 }
4231
4232
4233 /* Add back the always live regs in BB to LIVE.  */
4234
4235 static inline void
4236 df_simulate_fixup_sets (basic_block bb, bitmap live)
4237 {
4238   /* These regs are considered always live so if they end up dying
4239      because of some def, we need to bring the back again.  */
4240   if (df_has_eh_preds (bb))
4241     bitmap_ior_into (live, df->eh_block_artificial_uses);
4242   else
4243     bitmap_ior_into (live, df->regular_block_artificial_uses);
4244 }
4245
4246
4247 /* Apply the artificial uses and defs at the top of BB in a forwards
4248    direction.  */
4249
4250 void
4251 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
4252 {
4253   struct df_ref **def_rec;
4254   struct df_ref **use_rec;
4255   int bb_index = bb->index;
4256
4257   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4258     {
4259       struct df_ref *use = *use_rec;
4260       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4261         bitmap_set_bit (live, DF_REF_REGNO (use));
4262     }
4263
4264   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4265     {
4266       struct df_ref *def = *def_rec;
4267       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4268         bitmap_clear_bit (live, DF_REF_REGNO (def));
4269     }
4270 }
4271
4272
4273 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
4274
4275 void
4276 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
4277 {
4278   if (! INSN_P (insn))
4279     return;
4280
4281   df_simulate_uses (insn, live);
4282   df_simulate_defs (insn, live);
4283   df_simulate_fixup_sets (bb, live);
4284 }
4285
4286
4287 /* Apply the artificial uses and defs at the end of BB in a backwards
4288    direction.  */
4289
4290 void
4291 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
4292 {
4293   struct df_ref **def_rec;
4294   struct df_ref **use_rec;
4295   int bb_index = bb->index;
4296
4297   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
4298     {
4299       struct df_ref *def = *def_rec;
4300       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
4301         bitmap_clear_bit (live, DF_REF_REGNO (def));
4302     }
4303
4304   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
4305     {
4306       struct df_ref *use = *use_rec;
4307       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
4308         bitmap_set_bit (live, DF_REF_REGNO (use));
4309     }
4310 }
4311
4312
4313 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
4314
4315 void
4316 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
4317 {
4318   if (! INSN_P (insn))
4319     return;
4320
4321   df_simulate_defs (insn, live);
4322   df_simulate_uses (insn, live);
4323   df_simulate_fixup_sets (bb, live);
4324 }
4325
4326