gcc/df-problems.c

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