gcc/df-problems.c

   1 /* Standard problems for dataflow support routines.
   2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Originally contributed by Michael P. Hayes
   5              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
   6    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
   7              and Kenneth Zadeck (zadeck@naturalbridge.com).
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under
  12 the terms of the GNU General Public License as published by the Free
  13 Software Foundation; either version 3, or (at your option) any later
  14 version.
  15
  16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19 for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with GCC; see the file COPYING3.  If not see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "insn-config.h"
  32 #include "recog.h"
  33 #include "function.h"
  34 #include "regs.h"
  35 #include "output.h"
  36 #include "alloc-pool.h"
  37 #include "flags.h"
  38 #include "hard-reg-set.h"
  39 #include "basic-block.h"
  40 #include "sbitmap.h"
  41 #include "bitmap.h"
  42 #include "timevar.h"
  43 #include "df.h"
  44 #include "except.h"
  45 #include "dce.h"
  46 #include "vecprim.h"
  47
  48 /* Note that turning REG_DEAD_DEBUGGING on will cause
  49    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
  50    addresses in the dumps.  */
  51 #if 0
  52 #define REG_DEAD_DEBUGGING
  53 #endif
  54
  55 #define DF_SPARSE_THRESHOLD 32
  56
  57 static bitmap seen_in_block = NULL;
  58 static bitmap seen_in_insn = NULL;
  59
  60 \f
  61 /*----------------------------------------------------------------------------
  62    Public functions access functions for the dataflow problems.
  63 ----------------------------------------------------------------------------*/
  64 /* Get the live at out set for BB no matter what problem happens to be
  65    defined.  This function is used by the register allocators who
  66    choose different dataflow problems depending on the optimization
  67    level.  */
  68
  69 bitmap
  70 df_get_live_out (basic_block bb)
  71 {
  72   gcc_assert (df_lr);
  73
  74   if (df_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_live)
  91     return DF_LIVE_IN (bb);
  92   else
  93     return DF_LR_IN (bb);
  94 }
  95
  96 /*----------------------------------------------------------------------------
  97    Utility functions.
  98 ----------------------------------------------------------------------------*/
  99
 100 /* Generic versions to get the void* version of the block info.  Only
 101    used inside the problem instance vectors.  */
 102
 103 /* Grow the bb_info array.  */
 104
 105 void
 106 df_grow_bb_info (struct dataflow *dflow)
 107 {
 108   unsigned int new_size = last_basic_block + 1;
 109   if (dflow->block_info_size < new_size)
 110     {
 111       new_size += new_size / 4;
 112       dflow->block_info = xrealloc (dflow->block_info,
 113                                     new_size *sizeof (void*));
 114       memset (dflow->block_info + dflow->block_info_size, 0,
 115               (new_size - dflow->block_info_size) *sizeof (void *));
 116       dflow->block_info_size = new_size;
 117     }
 118 }
 119
 120 /* Dump a def-use or use-def chain for REF to FILE.  */
 121
 122 void
 123 df_chain_dump (struct df_link *link, FILE *file)
 124 {
 125   fprintf (file, "{ ");
 126   for (; link; link = link->next)
 127     {
 128       fprintf (file, "%c%d(bb %d insn %d) ",
 129                DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
 130                DF_REF_ID (link->ref),
 131                DF_REF_BBNO (link->ref),
 132                DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
 133     }
 134   fprintf (file, "}");
 135 }
 136
 137
 138 /* Print some basic block info as part of df_dump.  */
 139
 140 void
 141 df_print_bb_index (basic_block bb, FILE *file)
 142 {
 143   edge e;
 144   edge_iterator ei;
 145
 146   fprintf (file, "\n( ");
 147     FOR_EACH_EDGE (e, ei, bb->preds)
 148     {
 149       basic_block pred = e->src;
 150       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
 151     }
 152   fprintf (file, ")->[%d]->( ", bb->index);
 153   FOR_EACH_EDGE (e, ei, bb->succs)
 154     {
 155       basic_block succ = e->dest;
 156       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
 157     }
 158   fprintf (file, ")\n");
 159 }
 160
 161
 162
 163 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
 164    up correctly. */
 165
 166 static void
 167 df_set_seen (void)
 168 {
 169   seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
 170   seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
 171 }
 172
 173
 174 static void
 175 df_unset_seen (void)
 176 {
 177   BITMAP_FREE (seen_in_block);
 178   BITMAP_FREE (seen_in_insn);
 179 }
 180
 181
 182 \f
 183 /*----------------------------------------------------------------------------
 184    REACHING DEFINITIONS
 185
 186    Find the locations in the function where each definition site for a
 187    pseudo reaches.  In and out bitvectors are built for each basic
 188    block.  The id field in the ref is used to index into these sets.
 189    See df.h for details.
 190    ----------------------------------------------------------------------------*/
 191
 192 /* This problem plays a large number of games for the sake of
 193    efficiency.
 194
 195    1) The order of the bits in the bitvectors.  After the scanning
 196    phase, all of the defs are sorted.  All of the defs for the reg 0
 197    are first, followed by all defs for reg 1 and so on.
 198
 199    2) There are two kill sets, one if the number of defs is less or
 200    equal to DF_SPARSE_THRESHOLD and another if the number of defs is
 201    greater.
 202
 203    <= : Data is built directly in the kill set.
 204
 205    > : One level of indirection is used to keep from generating long
 206    strings of 1 bits in the kill sets.  Bitvectors that are indexed
 207    by the regnum are used to represent that there is a killing def
 208    for the register.  The confluence and transfer functions use
 209    these along with the bitmap_clear_range call to remove ranges of
 210    bits without actually generating a knockout vector.
 211
 212    The kill and sparse_kill and the dense_invalidated_by_call and
 213    sparse_invalidated_by_call both play this game.  */
 214
 215 /* Private data used to compute the solution for this problem.  These
 216    data structures are not accessible outside of this module.  */
 217 struct df_rd_problem_data
 218 {
 219   /* The set of defs to regs invalidated by call.  */
 220   bitmap sparse_invalidated_by_call;
 221   /* The set of defs to regs invalidate by call for rd.  */
 222   bitmap dense_invalidated_by_call;
 223   /* An obstack for the bitmaps we need for this problem.  */
 224   bitmap_obstack rd_bitmaps;
 225 };
 226
 227 /* Set basic block info.  */
 228
 229 static void
 230 df_rd_set_bb_info (unsigned int index,
 231                    struct df_rd_bb_info *bb_info)
 232 {
 233   gcc_assert (df_rd);
 234   gcc_assert (index < df_rd->block_info_size);
 235   df_rd->block_info[index] = bb_info;
 236 }
 237
 238
 239 /* Free basic block info.  */
 240
 241 static void
 242 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 243                     void *vbb_info)
 244 {
 245   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
 246   if (bb_info)
 247     {
 248       BITMAP_FREE (bb_info->kill);
 249       BITMAP_FREE (bb_info->sparse_kill);
 250       BITMAP_FREE (bb_info->gen);
 251       BITMAP_FREE (bb_info->in);
 252       BITMAP_FREE (bb_info->out);
 253       pool_free (df_rd->block_pool, bb_info);
 254     }
 255 }
 256
 257
 258 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
 259    not touched unless the block is new.  */
 260
 261 static void
 262 df_rd_alloc (bitmap all_blocks)
 263 {
 264   unsigned int bb_index;
 265   bitmap_iterator bi;
 266   struct df_rd_problem_data *problem_data;
 267
 268   if (!df_rd->block_pool)
 269     df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
 270                                            sizeof (struct df_rd_bb_info), 50);
 271
 272   if (df_rd->problem_data)
 273     {
 274       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 275       bitmap_clear (problem_data->sparse_invalidated_by_call);
 276       bitmap_clear (problem_data->dense_invalidated_by_call);
 277     }
 278   else
 279     {
 280       problem_data = XNEW (struct df_rd_problem_data);
 281       df_rd->problem_data = problem_data;
 282
 283       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
 284       problem_data->sparse_invalidated_by_call
 285         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 286       problem_data->dense_invalidated_by_call
 287         = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 288     }
 289
 290   df_grow_bb_info (df_rd);
 291
 292   /* Because of the clustering of all use sites for the same pseudo,
 293      we have to process all of the blocks before doing the
 294      analysis.  */
 295
 296   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 297     {
 298       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 299       if (bb_info)
 300         {
 301           bitmap_clear (bb_info->kill);
 302           bitmap_clear (bb_info->sparse_kill);
 303           bitmap_clear (bb_info->gen);
 304         }
 305       else
 306         {
 307           bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
 308           df_rd_set_bb_info (bb_index, bb_info);
 309           bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 310           bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 311           bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 312           bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 313           bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 314         }
 315     }
 316   df_rd->optional_p = true;
 317 }
 318
 319
 320 /* Process a list of DEFs for df_rd_bb_local_compute.  */
 321
 322 static void
 323 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
 324                                     struct df_ref **def_rec,
 325                                     enum df_ref_flags top_flag)
 326 {
 327   while (*def_rec)
 328     {
 329       struct df_ref *def = *def_rec;
 330       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
 331         {
 332           unsigned int regno = DF_REF_REGNO (def);
 333           unsigned int begin = DF_DEFS_BEGIN (regno);
 334           unsigned int n_defs = DF_DEFS_COUNT (regno);
 335
 336           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
 337               || (regno >= FIRST_PSEUDO_REGISTER))
 338             {
 339               /* Only the last def(s) for a regno in the block has any
 340                  effect.  */
 341               if (!bitmap_bit_p (seen_in_block, regno))
 342                 {
 343                   /* The first def for regno in insn gets to knock out the
 344                      defs from other instructions.  */
 345                   if ((!bitmap_bit_p (seen_in_insn, regno))
 346                       /* If the def is to only part of the reg, it does
 347                          not kill the other defs that reach here.  */
 348                       && (!(DF_REF_FLAGS (def) &
 349                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
 350                     {
 351                       if (n_defs > DF_SPARSE_THRESHOLD)
 352                         {
 353                           bitmap_set_bit (bb_info->sparse_kill, regno);
 354                           bitmap_clear_range(bb_info->gen, begin, n_defs);
 355                         }
 356                       else
 357                         {
 358                           bitmap_set_range (bb_info->kill, begin, n_defs);
 359                           bitmap_clear_range (bb_info->gen, begin, n_defs);
 360                         }
 361                     }
 362
 363                   bitmap_set_bit (seen_in_insn, regno);
 364                   /* All defs for regno in the instruction may be put into
 365                      the gen set.  */
 366                   if (!(DF_REF_FLAGS (def)
 367                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
 368                     bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
 369                 }
 370             }
 371         }
 372       def_rec++;
 373     }
 374 }
 375
 376 /* Compute local reaching def info for basic block BB.  */
 377
 378 static void
 379 df_rd_bb_local_compute (unsigned int bb_index)
 380 {
 381   basic_block bb = BASIC_BLOCK (bb_index);
 382   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 383   rtx insn;
 384
 385   bitmap_clear (seen_in_block);
 386   bitmap_clear (seen_in_insn);
 387
 388   /* Artificials are only hard regs.  */
 389   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 390     df_rd_bb_local_compute_process_def (bb_info,
 391                                         df_get_artificial_defs (bb_index),
 392                                         0);
 393
 394   FOR_BB_INSNS_REVERSE (bb, insn)
 395     {
 396       unsigned int uid = INSN_UID (insn);
 397
 398       if (!INSN_P (insn))
 399         continue;
 400
 401       df_rd_bb_local_compute_process_def (bb_info,
 402                                           DF_INSN_UID_DEFS (uid), 0);
 403
 404       /* This complex dance with the two bitmaps is required because
 405          instructions can assign twice to the same pseudo.  This
 406          generally happens with calls that will have one def for the
 407          result and another def for the clobber.  If only one vector
 408          is used and the clobber goes first, the result will be
 409          lost.  */
 410       bitmap_ior_into (seen_in_block, seen_in_insn);
 411       bitmap_clear (seen_in_insn);
 412     }
 413
 414   /* Process the artificial defs at the top of the block last since we
 415      are going backwards through the block and these are logically at
 416      the start.  */
 417   if (!(df->changeable_flags & DF_NO_HARD_REGS))
 418     df_rd_bb_local_compute_process_def (bb_info,
 419                                         df_get_artificial_defs (bb_index),
 420                                         DF_REF_AT_TOP);
 421 }
 422
 423
 424 /* Compute local reaching def info for each basic block within BLOCKS.  */
 425
 426 static void
 427 df_rd_local_compute (bitmap all_blocks)
 428 {
 429   unsigned int bb_index;
 430   bitmap_iterator bi;
 431   unsigned int regno;
 432   struct df_rd_problem_data *problem_data
 433     = (struct df_rd_problem_data *) df_rd->problem_data;
 434   bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 435   bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 436
 437   df_set_seen ();
 438
 439   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
 440
 441   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 442     {
 443       df_rd_bb_local_compute (bb_index);
 444     }
 445
 446   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
 447   EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
 448     {
 449       if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
 450         bitmap_set_bit (sparse_invalidated, regno);
 451       else
 452         bitmap_set_range (dense_invalidated,
 453                           DF_DEFS_BEGIN (regno),
 454                           DF_DEFS_COUNT (regno));
 455     }
 456   df_unset_seen ();
 457 }
 458
 459
 460 /* Initialize the solution bit vectors for problem.  */
 461
 462 static void
 463 df_rd_init_solution (bitmap all_blocks)
 464 {
 465   unsigned int bb_index;
 466   bitmap_iterator bi;
 467
 468   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 469     {
 470       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 471
 472       bitmap_copy (bb_info->out, bb_info->gen);
 473       bitmap_clear (bb_info->in);
 474     }
 475 }
 476
 477 /* In of target gets or of out of source.  */
 478
 479 static void
 480 df_rd_confluence_n (edge e)
 481 {
 482   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
 483   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
 484
 485   if (e->flags & EDGE_FAKE)
 486     return;
 487
 488   if (e->flags & EDGE_EH)
 489     {
 490       struct df_rd_problem_data *problem_data
 491         = (struct df_rd_problem_data *) df_rd->problem_data;
 492       bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
 493       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
 494       bitmap_iterator bi;
 495       unsigned int regno;
 496       bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
 497
 498       bitmap_copy (tmp, op2);
 499       bitmap_and_compl_into (tmp, dense_invalidated);
 500
 501       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
 502         {
 503           bitmap_clear_range (tmp,
 504                               DF_DEFS_BEGIN (regno),
 505                               DF_DEFS_COUNT (regno));
 506         }
 507       bitmap_ior_into (op1, tmp);
 508       BITMAP_FREE (tmp);
 509     }
 510   else
 511     bitmap_ior_into (op1, op2);
 512 }
 513
 514
 515 /* Transfer function.  */
 516
 517 static bool
 518 df_rd_transfer_function (int bb_index)
 519 {
 520   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
 521   unsigned int regno;
 522   bitmap_iterator bi;
 523   bitmap in = bb_info->in;
 524   bitmap out = bb_info->out;
 525   bitmap gen = bb_info->gen;
 526   bitmap kill = bb_info->kill;
 527   bitmap sparse_kill = bb_info->sparse_kill;
 528
 529   if (bitmap_empty_p (sparse_kill))
 530     return  bitmap_ior_and_compl (out, gen, in, kill);
 531   else
 532     {
 533       struct df_rd_problem_data *problem_data;
 534       bool changed = false;
 535       bitmap tmp;
 536
 537       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
 538          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
 539       problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
 540       tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
 541
 542       bitmap_copy (tmp, in);
 543       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
 544         {
 545           bitmap_clear_range (tmp,
 546                               DF_DEFS_BEGIN (regno),
 547                               DF_DEFS_COUNT (regno));
 548         }
 549       bitmap_and_compl_into (tmp, kill);
 550       bitmap_ior_into (tmp, gen);
 551       changed = !bitmap_equal_p (tmp, out);
 552       if (changed)
 553         {
 554           BITMAP_FREE (out);
 555           bb_info->out = tmp;
 556         }
 557       else
 558           BITMAP_FREE (tmp);
 559       return changed;
 560     }
 561 }
 562
 563
 564 /* Free all storage associated with the problem.  */
 565
 566 static void
 567 df_rd_free (void)
 568 {
 569   unsigned int i;
 570   struct df_rd_problem_data *problem_data
 571     = (struct df_rd_problem_data *) df_rd->problem_data;
 572
 573   if (problem_data)
 574     {
 575       for (i = 0; i < df_rd->block_info_size; i++)
 576         {
 577           struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
 578           if (bb_info)
 579             {
 580               BITMAP_FREE (bb_info->kill);
 581               BITMAP_FREE (bb_info->sparse_kill);
 582               BITMAP_FREE (bb_info->gen);
 583               BITMAP_FREE (bb_info->in);
 584               BITMAP_FREE (bb_info->out);
 585             }
 586         }
 587
 588       free_alloc_pool (df_rd->block_pool);
 589       BITMAP_FREE (problem_data->sparse_invalidated_by_call);
 590       BITMAP_FREE (problem_data->dense_invalidated_by_call);
 591       bitmap_obstack_release (&problem_data->rd_bitmaps);
 592
 593       df_rd->block_info_size = 0;
 594       free (df_rd->block_info);
 595       free (df_rd->problem_data);
 596     }
 597   free (df_rd);
 598 }
 599
 600
 601 /* Debugging info.  */
 602
 603 static void
 604 df_rd_start_dump (FILE *file)
 605 {
 606   struct df_rd_problem_data *problem_data
 607     = (struct df_rd_problem_data *) df_rd->problem_data;
 608   unsigned int m = DF_REG_SIZE(df);
 609   unsigned int regno;
 610
 611   if (!df_rd->block_info)
 612     return;
 613
 614   fprintf (file, ";; Reaching defs:\n\n");
 615
 616   fprintf (file, "  sparse invalidated \t");
 617   dump_bitmap (file, problem_data->sparse_invalidated_by_call);
 618   fprintf (file, "  dense invalidated \t");
 619   dump_bitmap (file, problem_data->dense_invalidated_by_call);
 620
 621   for (regno = 0; regno < m; regno++)
 622     if (DF_DEFS_COUNT (regno))
 623       fprintf (file, "%d[%d,%d] ", regno,
 624                DF_DEFS_BEGIN (regno),
 625                DF_DEFS_COUNT (regno));
 626   fprintf (file, "\n");
 627
 628 }
 629
 630
 631 /* Debugging info at top of bb.  */
 632
 633 static void
 634 df_rd_top_dump (basic_block bb, FILE *file)
 635 {
 636   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 637   if (!bb_info || !bb_info->in)
 638     return;
 639
 640   fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
 641   dump_bitmap (file, bb_info->in);
 642   fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
 643   dump_bitmap (file, bb_info->gen);
 644   fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
 645   dump_bitmap (file, bb_info->kill);
 646 }
 647
 648
 649 /* Debugging info at top of bb.  */
 650
 651 static void
 652 df_rd_bottom_dump (basic_block bb, FILE *file)
 653 {
 654   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
 655   if (!bb_info || !bb_info->out)
 656     return;
 657
 658   fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
 659   dump_bitmap (file, bb_info->out);
 660 }
 661
 662 /* All of the information associated with every instance of the problem.  */
 663
 664 static struct df_problem problem_RD =
 665 {
 666   DF_RD,                      /* Problem id.  */
 667   DF_FORWARD,                 /* Direction.  */
 668   df_rd_alloc,                /* Allocate the problem specific data.  */
 669   NULL,                       /* Reset global information.  */
 670   df_rd_free_bb_info,         /* Free basic block info.  */
 671   df_rd_local_compute,        /* Local compute function.  */
 672   df_rd_init_solution,        /* Init the solution specific data.  */
 673   df_worklist_dataflow,       /* Worklist solver.  */
 674   NULL,                       /* Confluence operator 0.  */
 675   df_rd_confluence_n,         /* Confluence operator n.  */
 676   df_rd_transfer_function,    /* Transfer function.  */
 677   NULL,                       /* Finalize function.  */
 678   df_rd_free,                 /* Free all of the problem information.  */
 679   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
 680   df_rd_start_dump,           /* Debugging.  */
 681   df_rd_top_dump,             /* Debugging start block.  */
 682   df_rd_bottom_dump,          /* Debugging end block.  */
 683   NULL,                       /* Incremental solution verify start.  */
 684   NULL,                       /* Incremental solution verify end.  */
 685   NULL,                       /* Dependent problem.  */
 686   TV_DF_RD,                   /* Timing variable.  */
 687   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
 688 };
 689
 690
 691
 692 /* Create a new DATAFLOW instance and add it to an existing instance
 693    of DF.  The returned structure is what is used to get at the
 694    solution.  */
 695
 696 void
 697 df_rd_add_problem (void)
 698 {
 699   df_add_problem (&problem_RD);
 700 }
 701
 702
 703 \f
 704 /*----------------------------------------------------------------------------
 705    LIVE REGISTERS
 706
 707    Find the locations in the function where any use of a pseudo can
 708    reach in the backwards direction.  In and out bitvectors are built
 709    for each basic block.  The regnum is used to index into these sets.
 710    See df.h for details.
 711    ----------------------------------------------------------------------------*/
 712
 713 /* Private data used to verify the solution for this problem.  */
 714 struct df_lr_problem_data
 715 {
 716   bitmap *in;
 717   bitmap *out;
 718 };
 719
 720
 721 /* Set basic block info.  */
 722
 723 static void
 724 df_lr_set_bb_info (unsigned int index,
 725                    struct df_lr_bb_info *bb_info)
 726 {
 727   gcc_assert (df_lr);
 728   gcc_assert (index < df_lr->block_info_size);
 729   df_lr->block_info[index] = bb_info;
 730 }
 731
 732
 733 /* Free basic block info.  */
 734
 735 static void
 736 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
 737                     void *vbb_info)
 738 {
 739   struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
 740   if (bb_info)
 741     {
 742       BITMAP_FREE (bb_info->use);
 743       BITMAP_FREE (bb_info->def);
 744       BITMAP_FREE (bb_info->in);
 745       BITMAP_FREE (bb_info->out);
 746       pool_free (df_lr->block_pool, bb_info);
 747     }
 748 }
 749
 750
 751 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
 752    not touched unless the block is new.  */
 753
 754 static void
 755 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 756 {
 757   unsigned int bb_index;
 758   bitmap_iterator bi;
 759
 760   if (!df_lr->block_pool)
 761     df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
 762                                            sizeof (struct df_lr_bb_info), 50);
 763
 764   df_grow_bb_info (df_lr);
 765
 766   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 767     {
 768       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 769       if (bb_info)
 770         {
 771           bitmap_clear (bb_info->def);
 772           bitmap_clear (bb_info->use);
 773         }
 774       else
 775         {
 776           bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
 777           df_lr_set_bb_info (bb_index, bb_info);
 778           bb_info->use = BITMAP_ALLOC (NULL);
 779           bb_info->def = BITMAP_ALLOC (NULL);
 780           bb_info->in = BITMAP_ALLOC (NULL);
 781           bb_info->out = BITMAP_ALLOC (NULL);
 782         }
 783     }
 784
 785   df_lr->optional_p = false;
 786 }
 787
 788
 789 /* Reset the global solution for recalculation.  */
 790
 791 static void
 792 df_lr_reset (bitmap all_blocks)
 793 {
 794   unsigned int bb_index;
 795   bitmap_iterator bi;
 796
 797   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 798     {
 799       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 800       gcc_assert (bb_info);
 801       bitmap_clear (bb_info->in);
 802       bitmap_clear (bb_info->out);
 803     }
 804 }
 805
 806
 807 /* Compute local live register info for basic block BB.  */
 808
 809 static void
 810 df_lr_bb_local_compute (unsigned int bb_index)
 811 {
 812   basic_block bb = BASIC_BLOCK (bb_index);
 813   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 814   rtx insn;
 815   struct df_ref **def_rec;
 816   struct df_ref **use_rec;
 817
 818   /* Process the registers set in an exception handler.  */
 819   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 820     {
 821       struct df_ref *def = *def_rec;
 822       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 823         {
 824           unsigned int dregno = DF_REF_REGNO (def);
 825           bitmap_set_bit (bb_info->def, dregno);
 826           bitmap_clear_bit (bb_info->use, dregno);
 827         }
 828     }
 829
 830   /* Process the hardware registers that are always live.  */
 831   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 832     {
 833       struct df_ref *use = *use_rec;
 834       /* Add use to set of uses in this BB.  */
 835       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 836         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 837     }
 838
 839   FOR_BB_INSNS_REVERSE (bb, insn)
 840     {
 841       unsigned int uid = INSN_UID (insn);
 842
 843       if (!INSN_P (insn))
 844         continue;
 845
 846       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 847         {
 848           struct df_ref *def = *def_rec;
 849           /* If the def is to only part of the reg, it does
 850              not kill the other defs that reach here.  */
 851           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 852             {
 853               unsigned int dregno = DF_REF_REGNO (def);
 854               bitmap_set_bit (bb_info->def, dregno);
 855               bitmap_clear_bit (bb_info->use, dregno);
 856             }
 857         }
 858
 859       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 860         {
 861           struct df_ref *use = *use_rec;
 862           /* Add use to set of uses in this BB.  */
 863           bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 864         }
 865     }
 866
 867   /* Process the registers set in an exception handler or the hard
 868      frame pointer if this block is the target of a non local
 869      goto.  */
 870   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 871     {
 872       struct df_ref *def = *def_rec;
 873       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 874         {
 875           unsigned int dregno = DF_REF_REGNO (def);
 876           bitmap_set_bit (bb_info->def, dregno);
 877           bitmap_clear_bit (bb_info->use, dregno);
 878         }
 879     }
 880
 881 #ifdef EH_USES
 882   /* Process the uses that are live into an exception handler.  */
 883   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 884     {
 885       struct df_ref *use = *use_rec;
 886       /* Add use to set of uses in this BB.  */
 887       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 888         bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
 889     }
 890 #endif
 891
 892   /* If the df_live problem is not defined, such as at -O0 and -O1, we
 893      still need to keep the luids up to date.  This is normally done
 894      in the df_live problem since this problem has a forwards
 895      scan.  */
 896   if (!df_live)
 897     df_recompute_luids (bb);
 898 }
 899
 900
 901 /* Compute local live register info for each basic block within BLOCKS.  */
 902
 903 static void
 904 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
 905 {
 906   unsigned int bb_index;
 907   bitmap_iterator bi;
 908
 909   bitmap_clear (df->hardware_regs_used);
 910
 911   /* The all-important stack pointer must always be live.  */
 912   bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
 913
 914   /* Before reload, there are a few registers that must be forced
 915      live everywhere -- which might not already be the case for
 916      blocks within infinite loops.  */
 917   if (!reload_completed)
 918     {
 919       /* Any reference to any pseudo before reload is a potential
 920          reference of the frame pointer.  */
 921       bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
 922
 923 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
 924       /* Pseudos with argument area equivalences may require
 925          reloading via the argument pointer.  */
 926       if (fixed_regs[ARG_POINTER_REGNUM])
 927         bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
 928 #endif
 929
 930       /* Any constant, or pseudo with constant equivalences, may
 931          require reloading from memory using the pic register.  */
 932       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
 933           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
 934         bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
 935     }
 936
 937   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
 938     {
 939       if (bb_index == EXIT_BLOCK)
 940         {
 941           /* The exit block is special for this problem and its bits are
 942              computed from thin air.  */
 943           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
 944           bitmap_copy (bb_info->use, df->exit_block_uses);
 945         }
 946       else
 947         df_lr_bb_local_compute (bb_index);
 948     }
 949
 950   bitmap_clear (df_lr->out_of_date_transfer_functions);
 951 }
 952
 953
 954 /* Initialize the solution vectors.  */
 955
 956 static void
 957 df_lr_init (bitmap all_blocks)
 958 {
 959   unsigned int bb_index;
 960   bitmap_iterator bi;
 961
 962   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
 963     {
 964       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
 965       bitmap_copy (bb_info->in, bb_info->use);
 966       bitmap_clear (bb_info->out);
 967     }
 968 }
 969
 970
 971 /* Confluence function that processes infinite loops.  This might be a
 972    noreturn function that throws.  And even if it isn't, getting the
 973    unwind info right helps debugging.  */
 974 static void
 975 df_lr_confluence_0 (basic_block bb)
 976 {
 977   bitmap op1 = df_lr_get_bb_info (bb->index)->out;
 978   if (bb != EXIT_BLOCK_PTR)
 979     bitmap_copy (op1, df->hardware_regs_used);
 980 }
 981
 982
 983 /* Confluence function that ignores fake edges.  */
 984
 985 static void
 986 df_lr_confluence_n (edge e)
 987 {
 988   bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
 989   bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
 990
 991   /* Call-clobbered registers die across exception and call edges.  */
 992   /* ??? Abnormal call edges ignored for the moment, as this gets
 993      confused by sibling call edges, which crashes reg-stack.  */
 994   if (e->flags & EDGE_EH)
 995     bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
 996   else
 997     bitmap_ior_into (op1, op2);
 998
 999   bitmap_ior_into (op1, df->hardware_regs_used);
1000 }
1001
1002
1003 /* Transfer function.  */
1004
1005 static bool
1006 df_lr_transfer_function (int bb_index)
1007 {
1008   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1009   bitmap in = bb_info->in;
1010   bitmap out = bb_info->out;
1011   bitmap use = bb_info->use;
1012   bitmap def = bb_info->def;
1013
1014   return bitmap_ior_and_compl (in, use, out, def);
1015 }
1016
1017
1018 /* Run the fast dce as a side effect of building LR.  */
1019
1020 static void
1021 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1022 {
1023   if (df->changeable_flags & DF_LR_RUN_DCE)
1024     {
1025       run_fast_df_dce ();
1026       if (df_lr->problem_data && df_lr->solutions_dirty)
1027         {
1028           /* If we are here, then it is because we are both verifying
1029           the solution and the dce changed the function.  In that case
1030           the verification info built will be wrong.  So we leave the
1031           dirty flag true so that the verifier will skip the checking
1032           part and just clean up.*/
1033           df_lr->solutions_dirty = true;
1034         }
1035       else
1036         df_lr->solutions_dirty = false;
1037     }
1038   else
1039     df_lr->solutions_dirty = false;
1040 }
1041
1042
1043 /* Free all storage associated with the problem.  */
1044
1045 static void
1046 df_lr_free (void)
1047 {
1048   if (df_lr->block_info)
1049     {
1050       unsigned int i;
1051       for (i = 0; i < df_lr->block_info_size; i++)
1052         {
1053           struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1054           if (bb_info)
1055             {
1056               BITMAP_FREE (bb_info->use);
1057               BITMAP_FREE (bb_info->def);
1058               BITMAP_FREE (bb_info->in);
1059               BITMAP_FREE (bb_info->out);
1060             }
1061         }
1062       free_alloc_pool (df_lr->block_pool);
1063
1064       df_lr->block_info_size = 0;
1065       free (df_lr->block_info);
1066     }
1067
1068   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1069   free (df_lr);
1070 }
1071
1072
1073 /* Debugging info at top of bb.  */
1074
1075 static void
1076 df_lr_top_dump (basic_block bb, FILE *file)
1077 {
1078   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1079   struct df_lr_problem_data *problem_data;
1080   if (!bb_info || !bb_info->in)
1081     return;
1082
1083   fprintf (file, ";; lr  in  \t");
1084   df_print_regset (file, bb_info->in);
1085   if (df_lr->problem_data)
1086     {
1087       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1088       fprintf (file, ";;  old in  \t");
1089       df_print_regset (file, problem_data->in[bb->index]);
1090     }
1091   fprintf (file, ";; lr  use \t");
1092   df_print_regset (file, bb_info->use);
1093   fprintf (file, ";; lr  def \t");
1094   df_print_regset (file, bb_info->def);
1095 }
1096
1097
1098 /* Debugging info at bottom of bb.  */
1099
1100 static void
1101 df_lr_bottom_dump (basic_block bb, FILE *file)
1102 {
1103   struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1104   struct df_lr_problem_data *problem_data;
1105   if (!bb_info || !bb_info->out)
1106     return;
1107
1108   fprintf (file, ";; lr  out \t");
1109   df_print_regset (file, bb_info->out);
1110   if (df_lr->problem_data)
1111     {
1112       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1113       fprintf (file, ";;  old out  \t");
1114       df_print_regset (file, problem_data->out[bb->index]);
1115     }
1116 }
1117
1118
1119 /* Build the datastructure to verify that the solution to the dataflow
1120    equations is not dirty.  */
1121
1122 static void
1123 df_lr_verify_solution_start (void)
1124 {
1125   basic_block bb;
1126   struct df_lr_problem_data *problem_data;
1127   if (df_lr->solutions_dirty)
1128     {
1129       df_lr->problem_data = NULL;
1130       return;
1131     }
1132
1133   /* Set it true so that the solution is recomputed.  */
1134   df_lr->solutions_dirty = true;
1135
1136   problem_data = XNEW (struct df_lr_problem_data);
1137   df_lr->problem_data = problem_data;
1138   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1139   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1140
1141   FOR_ALL_BB (bb)
1142     {
1143       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1144       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1145       bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1146       bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1147     }
1148 }
1149
1150
1151 /* Compare the saved datastructure and the new solution to the dataflow
1152    equations.  */
1153
1154 static void
1155 df_lr_verify_solution_end (void)
1156 {
1157   struct df_lr_problem_data *problem_data;
1158   basic_block bb;
1159
1160   if (df_lr->problem_data == NULL)
1161     return;
1162
1163   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1164
1165   if (df_lr->solutions_dirty)
1166     /* Do not check if the solution is still dirty.  See the comment
1167        in df_lr_finalize for details.  */
1168     df_lr->solutions_dirty = false;
1169   else
1170     FOR_ALL_BB (bb)
1171       {
1172         if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1173             || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1174           {
1175             /*df_dump (stderr);*/
1176             gcc_unreachable ();
1177           }
1178       }
1179
1180   /* Cannot delete them immediately because you may want to dump them
1181      if the comparison fails.  */
1182   FOR_ALL_BB (bb)
1183     {
1184       BITMAP_FREE (problem_data->in[bb->index]);
1185       BITMAP_FREE (problem_data->out[bb->index]);
1186     }
1187
1188   free (problem_data->in);
1189   free (problem_data->out);
1190   free (problem_data);
1191   df_lr->problem_data = NULL;
1192 }
1193
1194
1195 /* All of the information associated with every instance of the problem.  */
1196
1197 static struct df_problem problem_LR =
1198 {
1199   DF_LR,                      /* Problem id.  */
1200   DF_BACKWARD,                /* Direction.  */
1201   df_lr_alloc,                /* Allocate the problem specific data.  */
1202   df_lr_reset,                /* Reset global information.  */
1203   df_lr_free_bb_info,         /* Free basic block info.  */
1204   df_lr_local_compute,        /* Local compute function.  */
1205   df_lr_init,                 /* Init the solution specific data.  */
1206   df_worklist_dataflow,       /* Worklist solver.  */
1207   df_lr_confluence_0,         /* Confluence operator 0.  */
1208   df_lr_confluence_n,         /* Confluence operator n.  */
1209   df_lr_transfer_function,    /* Transfer function.  */
1210   df_lr_finalize,             /* Finalize function.  */
1211   df_lr_free,                 /* Free all of the problem information.  */
1212   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
1213   NULL,                       /* Debugging.  */
1214   df_lr_top_dump,             /* Debugging start block.  */
1215   df_lr_bottom_dump,          /* Debugging end block.  */
1216   df_lr_verify_solution_start,/* Incremental solution verify start.  */
1217   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
1218   NULL,                       /* Dependent problem.  */
1219   TV_DF_LR,                   /* Timing variable.  */
1220   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
1221 };
1222
1223
1224 /* Create a new DATAFLOW instance and add it to an existing instance
1225    of DF.  The returned structure is what is used to get at the
1226    solution.  */
1227
1228 void
1229 df_lr_add_problem (void)
1230 {
1231   df_add_problem (&problem_LR);
1232   /* These will be initialized when df_scan_blocks processes each
1233      block.  */
1234   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1235 }
1236
1237
1238 /* Verify that all of the lr related info is consistent and
1239    correct.  */
1240
1241 void
1242 df_lr_verify_transfer_functions (void)
1243 {
1244   basic_block bb;
1245   bitmap saved_def;
1246   bitmap saved_use;
1247   bitmap saved_adef;
1248   bitmap saved_ause;
1249   bitmap all_blocks;
1250
1251   if (!df)
1252     return;
1253
1254   saved_def = BITMAP_ALLOC (NULL);
1255   saved_use = BITMAP_ALLOC (NULL);
1256   saved_adef = BITMAP_ALLOC (NULL);
1257   saved_ause = BITMAP_ALLOC (NULL);
1258   all_blocks = BITMAP_ALLOC (NULL);
1259
1260   FOR_ALL_BB (bb)
1261     {
1262       struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1263       bitmap_set_bit (all_blocks, bb->index);
1264
1265       if (bb_info)
1266         {
1267           /* Make a copy of the transfer functions and then compute
1268              new ones to see if the transfer functions have
1269              changed.  */
1270           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1271                              bb->index))
1272             {
1273               bitmap_copy (saved_def, bb_info->def);
1274               bitmap_copy (saved_use, bb_info->use);
1275               bitmap_clear (bb_info->def);
1276               bitmap_clear (bb_info->use);
1277
1278               df_lr_bb_local_compute (bb->index);
1279               gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1280               gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1281             }
1282         }
1283       else
1284         {
1285           /* If we do not have basic block info, the block must be in
1286              the list of dirty blocks or else some one has added a
1287              block behind our backs. */
1288           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1289                                     bb->index));
1290         }
1291       /* Make sure no one created a block without following
1292          procedures.  */
1293       gcc_assert (df_scan_get_bb_info (bb->index));
1294     }
1295
1296   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1297   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1298                                          all_blocks));
1299
1300   BITMAP_FREE (saved_def);
1301   BITMAP_FREE (saved_use);
1302   BITMAP_FREE (saved_adef);
1303   BITMAP_FREE (saved_ause);
1304   BITMAP_FREE (all_blocks);
1305 }
1306
1307
1308 \f
1309 /*----------------------------------------------------------------------------
1310    LIVE AND MUST-INITIALIZED REGISTERS.
1311
1312    This problem first computes the IN and OUT bitvectors for the
1313    must-initialized registers problems, which is a forward problem.
1314    It gives the set of registers for which we MUST have an available
1315    definition on any path from the entry block to the entry/exit of
1316    a basic block.  Sets generate a definition, while clobbers kill
1317    a definition.
1318
1319    In and out bitvectors are built for each basic block and are indexed by
1320    regnum (see df.h for details).  In and out bitvectors in struct
1321    df_live_bb_info actually refers to the must-initialized problem;
1322
1323    Then, the in and out sets for the LIVE problem itself are computed.
1324    These are the logical AND of the IN and OUT sets from the LR problem
1325    and the must-initialized problem.
1326 ----------------------------------------------------------------------------*/
1327
1328 /* Private data used to verify the solution for this problem.  */
1329 struct df_live_problem_data
1330 {
1331   bitmap *in;
1332   bitmap *out;
1333 };
1334
1335 /* Scratch var used by transfer functions.  This is used to implement
1336    an optimization to reduce the amount of space used to compute the
1337    combined lr and live analysis.  */
1338 static bitmap df_live_scratch;
1339
1340 /* Set basic block info.  */
1341
1342 static void
1343 df_live_set_bb_info (unsigned int index,
1344                    struct df_live_bb_info *bb_info)
1345 {
1346   gcc_assert (df_live);
1347   gcc_assert (index < df_live->block_info_size);
1348   df_live->block_info[index] = bb_info;
1349 }
1350
1351
1352 /* Free basic block info.  */
1353
1354 static void
1355 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1356                     void *vbb_info)
1357 {
1358   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1359   if (bb_info)
1360     {
1361       BITMAP_FREE (bb_info->gen);
1362       BITMAP_FREE (bb_info->kill);
1363       BITMAP_FREE (bb_info->in);
1364       BITMAP_FREE (bb_info->out);
1365       pool_free (df_live->block_pool, bb_info);
1366     }
1367 }
1368
1369
1370 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1371    not touched unless the block is new.  */
1372
1373 static void
1374 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1375 {
1376   unsigned int bb_index;
1377   bitmap_iterator bi;
1378
1379   if (!df_live->block_pool)
1380     df_live->block_pool = create_alloc_pool ("df_live_block pool",
1381                                            sizeof (struct df_live_bb_info), 100);
1382   if (!df_live_scratch)
1383     df_live_scratch = BITMAP_ALLOC (NULL);
1384
1385   df_grow_bb_info (df_live);
1386
1387   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1388     {
1389       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1390       if (bb_info)
1391         {
1392           bitmap_clear (bb_info->kill);
1393           bitmap_clear (bb_info->gen);
1394         }
1395       else
1396         {
1397           bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1398           df_live_set_bb_info (bb_index, bb_info);
1399           bb_info->kill = BITMAP_ALLOC (NULL);
1400           bb_info->gen = BITMAP_ALLOC (NULL);
1401           bb_info->in = BITMAP_ALLOC (NULL);
1402           bb_info->out = BITMAP_ALLOC (NULL);
1403         }
1404     }
1405   df_live->optional_p = (optimize <= 1);
1406 }
1407
1408
1409 /* Reset the global solution for recalculation.  */
1410
1411 static void
1412 df_live_reset (bitmap all_blocks)
1413 {
1414   unsigned int bb_index;
1415   bitmap_iterator bi;
1416
1417   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1418     {
1419       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1420       gcc_assert (bb_info);
1421       bitmap_clear (bb_info->in);
1422       bitmap_clear (bb_info->out);
1423     }
1424 }
1425
1426
1427 /* Compute local uninitialized register info for basic block BB.  */
1428
1429 static void
1430 df_live_bb_local_compute (unsigned int bb_index)
1431 {
1432   basic_block bb = BASIC_BLOCK (bb_index);
1433   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1434   rtx insn;
1435   struct df_ref **def_rec;
1436   int luid = 0;
1437
1438   FOR_BB_INSNS (bb, insn)
1439     {
1440       unsigned int uid = INSN_UID (insn);
1441       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1442
1443       /* Inserting labels does not always trigger the incremental
1444          rescanning.  */
1445       if (!insn_info)
1446         {
1447           gcc_assert (!INSN_P (insn));
1448           df_insn_create_insn_record (insn);
1449         }
1450
1451       DF_INSN_LUID (insn) = luid;
1452       if (!INSN_P (insn))
1453         continue;
1454
1455       luid++;
1456       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1457         {
1458           struct df_ref *def = *def_rec;
1459           unsigned int regno = DF_REF_REGNO (def);
1460
1461           if (DF_REF_FLAGS_IS_SET (def,
1462                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1463             /* All partial or conditional def
1464                seen are included in the gen set. */
1465             bitmap_set_bit (bb_info->gen, regno);
1466           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1467             /* Only must clobbers for the entire reg destroy the
1468                value.  */
1469             bitmap_set_bit (bb_info->kill, regno);
1470           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1471             bitmap_set_bit (bb_info->gen, regno);
1472         }
1473     }
1474
1475   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1476     {
1477       struct df_ref *def = *def_rec;
1478       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1479     }
1480 }
1481
1482
1483 /* Compute local uninitialized register info.  */
1484
1485 static void
1486 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1487 {
1488   unsigned int bb_index;
1489   bitmap_iterator bi;
1490
1491   df_grow_insn_info ();
1492
1493   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1494                             0, bb_index, bi)
1495     {
1496       df_live_bb_local_compute (bb_index);
1497     }
1498
1499   bitmap_clear (df_live->out_of_date_transfer_functions);
1500 }
1501
1502
1503 /* Initialize the solution vectors.  */
1504
1505 static void
1506 df_live_init (bitmap all_blocks)
1507 {
1508   unsigned int bb_index;
1509   bitmap_iterator bi;
1510
1511   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1512     {
1513       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1514       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1515
1516       /* No register may reach a location where it is not used.  Thus
1517          we trim the rr result to the places where it is used.  */
1518       bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1519       bitmap_clear (bb_info->in);
1520     }
1521 }
1522
1523 /* Forward confluence function that ignores fake edges.  */
1524
1525 static void
1526 df_live_confluence_n (edge e)
1527 {
1528   bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1529   bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1530
1531   if (e->flags & EDGE_FAKE)
1532     return;
1533
1534   bitmap_ior_into (op1, op2);
1535 }
1536
1537
1538 /* Transfer function for the forwards must-initialized problem.  */
1539
1540 static bool
1541 df_live_transfer_function (int bb_index)
1542 {
1543   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1544   struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1545   bitmap in = bb_info->in;
1546   bitmap out = bb_info->out;
1547   bitmap gen = bb_info->gen;
1548   bitmap kill = bb_info->kill;
1549
1550   /* We need to use a scratch set here so that the value returned from
1551      this function invocation properly reflects if the sets changed in
1552      a significant way; i.e. not just because the lr set was anded
1553      in.  */
1554   bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1555   /* No register may reach a location where it is not used.  Thus
1556      we trim the rr result to the places where it is used.  */
1557   bitmap_and_into (in, bb_lr_info->in);
1558
1559   return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1560 }
1561
1562
1563 /* And the LR info with the must-initialized registers, to produce the LIVE info.  */
1564
1565 static void
1566 df_live_finalize (bitmap all_blocks)
1567 {
1568
1569   if (df_live->solutions_dirty)
1570     {
1571       bitmap_iterator bi;
1572       unsigned int bb_index;
1573
1574       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1575         {
1576           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1577           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1578
1579           /* No register may reach a location where it is not used.  Thus
1580              we trim the rr result to the places where it is used.  */
1581           bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1582           bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1583         }
1584
1585       df_live->solutions_dirty = false;
1586     }
1587 }
1588
1589
1590 /* Free all storage associated with the problem.  */
1591
1592 static void
1593 df_live_free (void)
1594 {
1595   if (df_live->block_info)
1596     {
1597       unsigned int i;
1598
1599       for (i = 0; i < df_live->block_info_size; i++)
1600         {
1601           struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1602           if (bb_info)
1603             {
1604               BITMAP_FREE (bb_info->gen);
1605               BITMAP_FREE (bb_info->kill);
1606               BITMAP_FREE (bb_info->in);
1607               BITMAP_FREE (bb_info->out);
1608             }
1609         }
1610
1611       free_alloc_pool (df_live->block_pool);
1612       df_live->block_info_size = 0;
1613       free (df_live->block_info);
1614
1615       if (df_live_scratch)
1616         BITMAP_FREE (df_live_scratch);
1617     }
1618   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1619   free (df_live);
1620 }
1621
1622
1623 /* Debugging info at top of bb.  */
1624
1625 static void
1626 df_live_top_dump (basic_block bb, FILE *file)
1627 {
1628   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1629   struct df_live_problem_data *problem_data;
1630
1631   if (!bb_info || !bb_info->in)
1632     return;
1633
1634   fprintf (file, ";; live  in  \t");
1635   df_print_regset (file, bb_info->in);
1636   if (df_live->problem_data)
1637     {
1638       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1639       fprintf (file, ";;  old in  \t");
1640       df_print_regset (file, problem_data->in[bb->index]);
1641     }
1642   fprintf (file, ";; live  gen \t");
1643   df_print_regset (file, bb_info->gen);
1644   fprintf (file, ";; live  kill\t");
1645   df_print_regset (file, bb_info->kill);
1646 }
1647
1648
1649 /* Debugging info at bottom of bb.  */
1650
1651 static void
1652 df_live_bottom_dump (basic_block bb, FILE *file)
1653 {
1654   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1655   struct df_live_problem_data *problem_data;
1656
1657   if (!bb_info || !bb_info->out)
1658     return;
1659
1660   fprintf (file, ";; live  out \t");
1661   df_print_regset (file, bb_info->out);
1662   if (df_live->problem_data)
1663     {
1664       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1665       fprintf (file, ";;  old out  \t");
1666       df_print_regset (file, problem_data->out[bb->index]);
1667     }
1668 }
1669
1670
1671 /* Build the datastructure to verify that the solution to the dataflow
1672    equations is not dirty.  */
1673
1674 static void
1675 df_live_verify_solution_start (void)
1676 {
1677   basic_block bb;
1678   struct df_live_problem_data *problem_data;
1679   if (df_live->solutions_dirty)
1680     {
1681       df_live->problem_data = NULL;
1682       return;
1683     }
1684
1685   /* Set it true so that the solution is recomputed.  */
1686   df_live->solutions_dirty = true;
1687
1688   problem_data = XNEW (struct df_live_problem_data);
1689   df_live->problem_data = problem_data;
1690   problem_data->in = XNEWVEC (bitmap, last_basic_block);
1691   problem_data->out = XNEWVEC (bitmap, last_basic_block);
1692
1693   FOR_ALL_BB (bb)
1694     {
1695       problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1696       problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1697       bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1698       bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1699     }
1700 }
1701
1702
1703 /* Compare the saved datastructure and the new solution to the dataflow
1704    equations.  */
1705
1706 static void
1707 df_live_verify_solution_end (void)
1708 {
1709   struct df_live_problem_data *problem_data;
1710   basic_block bb;
1711
1712   if (df_live->problem_data == NULL)
1713     return;
1714
1715   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1716
1717   FOR_ALL_BB (bb)
1718     {
1719       if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1720           || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1721         {
1722           /*df_dump (stderr);*/
1723           gcc_unreachable ();
1724         }
1725     }
1726
1727   /* Cannot delete them immediately because you may want to dump them
1728      if the comparison fails.  */
1729   FOR_ALL_BB (bb)
1730     {
1731       BITMAP_FREE (problem_data->in[bb->index]);
1732       BITMAP_FREE (problem_data->out[bb->index]);
1733     }
1734
1735   free (problem_data->in);
1736   free (problem_data->out);
1737   free (problem_data);
1738   df_live->problem_data = NULL;
1739 }
1740
1741
1742 /* All of the information associated with every instance of the problem.  */
1743
1744 static struct df_problem problem_LIVE =
1745 {
1746   DF_LIVE,                      /* Problem id.  */
1747   DF_FORWARD,                   /* Direction.  */
1748   df_live_alloc,                /* Allocate the problem specific data.  */
1749   df_live_reset,                /* Reset global information.  */
1750   df_live_free_bb_info,         /* Free basic block info.  */
1751   df_live_local_compute,        /* Local compute function.  */
1752   df_live_init,                 /* Init the solution specific data.  */
1753   df_worklist_dataflow,         /* Worklist solver.  */
1754   NULL,                         /* Confluence operator 0.  */
1755   df_live_confluence_n,         /* Confluence operator n.  */
1756   df_live_transfer_function,    /* Transfer function.  */
1757   df_live_finalize,             /* Finalize function.  */
1758   df_live_free,                 /* Free all of the problem information.  */
1759   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1760   NULL,                         /* Debugging.  */
1761   df_live_top_dump,             /* Debugging start block.  */
1762   df_live_bottom_dump,          /* Debugging end block.  */
1763   df_live_verify_solution_start,/* Incremental solution verify start.  */
1764   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1765   &problem_LR,                  /* Dependent problem.  */
1766   TV_DF_LIVE,                   /* Timing variable.  */
1767   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1768 };
1769
1770
1771 /* Create a new DATAFLOW instance and add it to an existing instance
1772    of DF.  The returned structure is what is used to get at the
1773    solution.  */
1774
1775 void
1776 df_live_add_problem (void)
1777 {
1778   df_add_problem (&problem_LIVE);
1779   /* These will be initialized when df_scan_blocks processes each
1780      block.  */
1781   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1782 }
1783
1784
1785 /* Set all of the blocks as dirty.  This needs to be done if this
1786    problem is added after all of the insns have been scanned.  */
1787
1788 void
1789 df_live_set_all_dirty (void)
1790 {
1791   basic_block bb;
1792   FOR_ALL_BB (bb)
1793     bitmap_set_bit (df_live->out_of_date_transfer_functions,
1794                     bb->index);
1795 }
1796
1797
1798 /* Verify that all of the lr related info is consistent and
1799    correct.  */
1800
1801 void
1802 df_live_verify_transfer_functions (void)
1803 {
1804   basic_block bb;
1805   bitmap saved_gen;
1806   bitmap saved_kill;
1807   bitmap all_blocks;
1808
1809   if (!df)
1810     return;
1811
1812   saved_gen = BITMAP_ALLOC (NULL);
1813   saved_kill = BITMAP_ALLOC (NULL);
1814   all_blocks = BITMAP_ALLOC (NULL);
1815
1816   df_grow_insn_info ();
1817
1818   FOR_ALL_BB (bb)
1819     {
1820       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1821       bitmap_set_bit (all_blocks, bb->index);
1822
1823       if (bb_info)
1824         {
1825           /* Make a copy of the transfer functions and then compute
1826              new ones to see if the transfer functions have
1827              changed.  */
1828           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1829                              bb->index))
1830             {
1831               bitmap_copy (saved_gen, bb_info->gen);
1832               bitmap_copy (saved_kill, bb_info->kill);
1833               bitmap_clear (bb_info->gen);
1834               bitmap_clear (bb_info->kill);
1835
1836               df_live_bb_local_compute (bb->index);
1837               gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1838               gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1839             }
1840         }
1841       else
1842         {
1843           /* If we do not have basic block info, the block must be in
1844              the list of dirty blocks or else some one has added a
1845              block behind our backs. */
1846           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1847                                     bb->index));
1848         }
1849       /* Make sure no one created a block without following
1850          procedures.  */
1851       gcc_assert (df_scan_get_bb_info (bb->index));
1852     }
1853
1854   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1855   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1856                                          all_blocks));
1857   BITMAP_FREE (saved_gen);
1858   BITMAP_FREE (saved_kill);
1859   BITMAP_FREE (all_blocks);
1860 }
1861 \f
1862 /*----------------------------------------------------------------------------
1863    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1864
1865    Link either the defs to the uses and / or the uses to the defs.
1866
1867    These problems are set up like the other dataflow problems so that
1868    they nicely fit into the framework.  They are much simpler and only
1869    involve a single traversal of instructions and an examination of
1870    the reaching defs information (the dependent problem).
1871 ----------------------------------------------------------------------------*/
1872
1873 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1874
1875 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1876
1877 struct df_link *
1878 df_chain_create (struct df_ref *src, struct df_ref *dst)
1879 {
1880   struct df_link *head = DF_REF_CHAIN (src);
1881   struct df_link *link = pool_alloc (df_chain->block_pool);;
1882
1883   DF_REF_CHAIN (src) = link;
1884   link->next = head;
1885   link->ref = dst;
1886   return link;
1887 }
1888
1889
1890 /* Delete any du or ud chains that start at REF and point to
1891    TARGET.  */
1892 static void
1893 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1894 {
1895   struct df_link *chain = DF_REF_CHAIN (ref);
1896   struct df_link *prev = NULL;
1897
1898   while (chain)
1899     {
1900       if (chain->ref == target)
1901         {
1902           if (prev)
1903             prev->next = chain->next;
1904           else
1905             DF_REF_CHAIN (ref) = chain->next;
1906           pool_free (df_chain->block_pool, chain);
1907           return;
1908         }
1909       prev = chain;
1910       chain = chain->next;
1911     }
1912 }
1913
1914
1915 /* Delete a du or ud chain that leave or point to REF.  */
1916
1917 void
1918 df_chain_unlink (struct df_ref *ref)
1919 {
1920   struct df_link *chain = DF_REF_CHAIN (ref);
1921   while (chain)
1922     {
1923       struct df_link *next = chain->next;
1924       /* Delete the other side if it exists.  */
1925       df_chain_unlink_1 (chain->ref, ref);
1926       pool_free (df_chain->block_pool, chain);
1927       chain = next;
1928     }
1929   DF_REF_CHAIN (ref) = NULL;
1930 }
1931
1932
1933 /* Copy the du or ud chain starting at FROM_REF and attach it to
1934    TO_REF.  */
1935
1936 void
1937 df_chain_copy (struct df_ref *to_ref,
1938                struct df_link *from_ref)
1939 {
1940   while (from_ref)
1941     {
1942       df_chain_create (to_ref, from_ref->ref);
1943       from_ref = from_ref->next;
1944     }
1945 }
1946
1947
1948 /* Remove this problem from the stack of dataflow problems.  */
1949
1950 static void
1951 df_chain_remove_problem (void)
1952 {
1953   bitmap_iterator bi;
1954   unsigned int bb_index;
1955
1956   /* Wholesale destruction of the old chains.  */
1957   if (df_chain->block_pool)
1958     free_alloc_pool (df_chain->block_pool);
1959
1960   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1961     {
1962       rtx insn;
1963       struct df_ref **def_rec;
1964       struct df_ref **use_rec;
1965       basic_block bb = BASIC_BLOCK (bb_index);
1966
1967       if (df_chain_problem_p (DF_DU_CHAIN))
1968         for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1969           DF_REF_CHAIN (*def_rec) = NULL;
1970       if (df_chain_problem_p (DF_UD_CHAIN))
1971         for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1972           DF_REF_CHAIN (*use_rec) = NULL;
1973
1974       FOR_BB_INSNS (bb, insn)
1975         {
1976           unsigned int uid = INSN_UID (insn);
1977
1978           if (INSN_P (insn))
1979             {
1980               if (df_chain_problem_p (DF_DU_CHAIN))
1981                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1982                   DF_REF_CHAIN (*def_rec) = NULL;
1983               if (df_chain_problem_p (DF_UD_CHAIN))
1984                 {
1985                   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1986                     DF_REF_CHAIN (*use_rec) = NULL;
1987                   for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1988                     DF_REF_CHAIN (*use_rec) = NULL;
1989                 }
1990             }
1991         }
1992     }
1993
1994   bitmap_clear (df_chain->out_of_date_transfer_functions);
1995   df_chain->block_pool = NULL;
1996 }
1997
1998
1999 /* Remove the chain problem completely.  */
2000
2001 static void
2002 df_chain_fully_remove_problem (void)
2003 {
2004   df_chain_remove_problem ();
2005   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2006   free (df_chain);
2007 }
2008
2009
2010 /* Create def-use or use-def chains.  */
2011
2012 static void
2013 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2014 {
2015   df_chain_remove_problem ();
2016   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2017                                          sizeof (struct df_link), 50);
2018   df_chain->optional_p = true;
2019 }
2020
2021
2022 /* Reset all of the chains when the set of basic blocks changes.  */
2023
2024 static void
2025 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2026 {
2027   df_chain_remove_problem ();
2028 }
2029
2030
2031 /* Create the chains for a list of USEs.  */
2032
2033 static void
2034 df_chain_create_bb_process_use (bitmap local_rd,
2035                                 struct df_ref **use_rec,
2036                                 enum df_ref_flags top_flag)
2037 {
2038   bitmap_iterator bi;
2039   unsigned int def_index;
2040
2041   while (*use_rec)
2042     {
2043       struct df_ref *use = *use_rec;
2044       unsigned int uregno = DF_REF_REGNO (use);
2045       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2046           || (uregno >= FIRST_PSEUDO_REGISTER))
2047         {
2048           /* Do not want to go through this for an uninitialized var.  */
2049           int count = DF_DEFS_COUNT (uregno);
2050           if (count)
2051             {
2052               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2053                 {
2054                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2055                   unsigned int last_index = first_index + count - 1;
2056
2057                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2058                     {
2059                       struct df_ref *def;
2060                       if (def_index > last_index)
2061                         break;
2062
2063                       def = DF_DEFS_GET (def_index);
2064                       if (df_chain_problem_p (DF_DU_CHAIN))
2065                         df_chain_create (def, use);
2066                       if (df_chain_problem_p (DF_UD_CHAIN))
2067                         df_chain_create (use, def);
2068                     }
2069                 }
2070             }
2071         }
2072
2073       use_rec++;
2074     }
2075 }
2076
2077
2078 /* Create chains from reaching defs bitmaps for basic block BB.  */
2079
2080 static void
2081 df_chain_create_bb (unsigned int bb_index)
2082 {
2083   basic_block bb = BASIC_BLOCK (bb_index);
2084   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2085   rtx insn;
2086   bitmap cpy = BITMAP_ALLOC (NULL);
2087   struct df_ref **def_rec;
2088
2089   bitmap_copy (cpy, bb_info->in);
2090   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2091
2092   /* Since we are going forwards, process the artificial uses first
2093      then the artificial defs second.  */
2094
2095 #ifdef EH_USES
2096   /* Create the chains for the artificial uses from the EH_USES at the
2097      beginning of the block.  */
2098
2099   /* Artificials are only hard regs.  */
2100   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2101     df_chain_create_bb_process_use (cpy,
2102                                     df_get_artificial_uses (bb->index),
2103                                     DF_REF_AT_TOP);
2104 #endif
2105
2106   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2107     {
2108       struct df_ref *def = *def_rec;
2109       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2110         {
2111           unsigned int dregno = DF_REF_REGNO (def);
2112           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2113             bitmap_clear_range (cpy,
2114                                 DF_DEFS_BEGIN (dregno),
2115                                 DF_DEFS_COUNT (dregno));
2116           bitmap_set_bit (cpy, DF_REF_ID (def));
2117         }
2118     }
2119
2120   /* Process the regular instructions next.  */
2121   FOR_BB_INSNS (bb, insn)
2122     {
2123       struct df_ref **def_rec;
2124       unsigned int uid = INSN_UID (insn);
2125
2126       if (!INSN_P (insn))
2127         continue;
2128
2129       /* Now scan the uses and link them up with the defs that remain
2130          in the cpy vector.  */
2131
2132       df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2133
2134       if (df->changeable_flags & DF_EQ_NOTES)
2135         df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2136
2137
2138       /* Since we are going forwards, process the defs second.  This
2139          pass only changes the bits in cpy.  */
2140       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2141         {
2142           struct df_ref *def = *def_rec;
2143           unsigned int dregno = DF_REF_REGNO (def);
2144           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2145               || (dregno >= FIRST_PSEUDO_REGISTER))
2146             {
2147               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2148                 bitmap_clear_range (cpy,
2149                                     DF_DEFS_BEGIN (dregno),
2150                                     DF_DEFS_COUNT (dregno));
2151               if (!(DF_REF_FLAGS (def)
2152                     & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2153                 bitmap_set_bit (cpy, DF_REF_ID (def));
2154             }
2155         }
2156     }
2157
2158   /* Create the chains for the artificial uses of the hard registers
2159      at the end of the block.  */
2160   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2161     df_chain_create_bb_process_use (cpy,
2162                                     df_get_artificial_uses (bb->index),
2163                                     0);
2164
2165   BITMAP_FREE (cpy);
2166 }
2167
2168 /* Create def-use chains from reaching use bitmaps for basic blocks
2169    in BLOCKS.  */
2170
2171 static void
2172 df_chain_finalize (bitmap all_blocks)
2173 {
2174   unsigned int bb_index;
2175   bitmap_iterator bi;
2176
2177   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2178     {
2179       df_chain_create_bb (bb_index);
2180     }
2181 }
2182
2183
2184 /* Free all storage associated with the problem.  */
2185
2186 static void
2187 df_chain_free (void)
2188 {
2189   free_alloc_pool (df_chain->block_pool);
2190   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2191   free (df_chain);
2192 }
2193
2194
2195 /* Debugging info.  */
2196
2197 static void
2198 df_chain_top_dump (basic_block bb, FILE *file)
2199 {
2200   if (df_chain_problem_p (DF_DU_CHAIN))
2201     {
2202       rtx insn;
2203       struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2204       if (*def_rec)
2205         {
2206
2207           fprintf (file, ";;  DU chains for artificial defs\n");
2208           while (*def_rec)
2209             {
2210               struct df_ref *def = *def_rec;
2211               fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2212               df_chain_dump (DF_REF_CHAIN (def), file);
2213               fprintf (file, "\n");
2214               def_rec++;
2215             }
2216         }
2217
2218       FOR_BB_INSNS (bb, insn)
2219         {
2220           unsigned int uid = INSN_UID (insn);
2221           if (INSN_P (insn))
2222             {
2223               def_rec = DF_INSN_UID_DEFS (uid);
2224               if (*def_rec)
2225                 {
2226                   fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2227                            DF_INSN_LUID (insn), uid);
2228
2229                   while (*def_rec)
2230                     {
2231                       struct df_ref *def = *def_rec;
2232                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2233                       if (def->flags & DF_REF_READ_WRITE)
2234                         fprintf (file, "read/write ");
2235                       df_chain_dump (DF_REF_CHAIN (def), file);
2236                       fprintf (file, "\n");
2237                       def_rec++;
2238                     }
2239                 }
2240             }
2241         }
2242     }
2243 }
2244
2245
2246 static void
2247 df_chain_bottom_dump (basic_block bb, FILE *file)
2248 {
2249   if (df_chain_problem_p (DF_UD_CHAIN))
2250     {
2251       rtx insn;
2252       struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2253
2254       if (*use_rec)
2255         {
2256           fprintf (file, ";;  UD chains for artificial uses\n");
2257           while (*use_rec)
2258             {
2259               struct df_ref *use = *use_rec;
2260               fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2261               df_chain_dump (DF_REF_CHAIN (use), file);
2262               fprintf (file, "\n");
2263               use_rec++;
2264             }
2265         }
2266
2267       FOR_BB_INSNS (bb, insn)
2268         {
2269           unsigned int uid = INSN_UID (insn);
2270           if (INSN_P (insn))
2271             {
2272               struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2273               use_rec = DF_INSN_UID_USES (uid);
2274               if (*use_rec || *eq_use_rec)
2275                 {
2276                   fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2277                            DF_INSN_LUID (insn), uid);
2278
2279                   while (*use_rec)
2280                     {
2281                       struct df_ref *use = *use_rec;
2282                       fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2283                       if (use->flags & DF_REF_READ_WRITE)
2284                         fprintf (file, "read/write ");
2285                       df_chain_dump (DF_REF_CHAIN (use), file);
2286                       fprintf (file, "\n");
2287                       use_rec++;
2288                     }
2289                   while (*eq_use_rec)
2290                     {
2291                       struct df_ref *use = *eq_use_rec;
2292                       fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2293                       df_chain_dump (DF_REF_CHAIN (use), file);
2294                       fprintf (file, "\n");
2295                       eq_use_rec++;
2296                     }
2297                 }
2298             }
2299         }
2300     }
2301 }
2302
2303
2304 static struct df_problem problem_CHAIN =
2305 {
2306   DF_CHAIN,                   /* Problem id.  */
2307   DF_NONE,                    /* Direction.  */
2308   df_chain_alloc,             /* Allocate the problem specific data.  */
2309   df_chain_reset,             /* Reset global information.  */
2310   NULL,                       /* Free basic block info.  */
2311   NULL,                       /* Local compute function.  */
2312   NULL,                       /* Init the solution specific data.  */
2313   NULL,                       /* Iterative solver.  */
2314   NULL,                       /* Confluence operator 0.  */
2315   NULL,                       /* Confluence operator n.  */
2316   NULL,                       /* Transfer function.  */
2317   df_chain_finalize,          /* Finalize function.  */
2318   df_chain_free,              /* Free all of the problem information.  */
2319   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2320   NULL,                       /* Debugging.  */
2321   df_chain_top_dump,          /* Debugging start block.  */
2322   df_chain_bottom_dump,       /* Debugging end block.  */
2323   NULL,                       /* Incremental solution verify start.  */
2324   NULL,                       /* Incremental solution verify end.  */
2325   &problem_RD,                /* Dependent problem.  */
2326   TV_DF_CHAIN,                /* Timing variable.  */
2327   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2328 };
2329
2330
2331 /* Create a new DATAFLOW instance and add it to an existing instance
2332    of DF.  The returned structure is what is used to get at the
2333    solution.  */
2334
2335 void
2336 df_chain_add_problem (enum df_chain_flags chain_flags)
2337 {
2338   df_add_problem (&problem_CHAIN);
2339   df_chain->local_flags = (unsigned int)chain_flags;
2340   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2341 }
2342
2343 #undef df_chain_problem_p
2344
2345 \f
2346 /*----------------------------------------------------------------------------
2347    This pass computes REG_DEAD and REG_UNUSED notes.
2348    ----------------------------------------------------------------------------*/
2349
2350 static void
2351 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2352 {
2353   df_note->optional_p = true;
2354 }
2355
2356 #ifdef REG_DEAD_DEBUGGING
2357 static void
2358 df_print_note (const char *prefix, rtx insn, rtx note)
2359 {
2360   if (dump_file)
2361     {
2362       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2363       print_rtl (dump_file, note);
2364       fprintf (dump_file, "\n");
2365     }
2366 }
2367 #endif
2368
2369
2370 /* After reg-stack, the x86 floating point stack regs are difficult to
2371    analyze because of all of the pushes, pops and rotations.  Thus, we
2372    just leave the notes alone. */
2373
2374 #ifdef STACK_REGS
2375 static inline bool
2376 df_ignore_stack_reg (int regno)
2377 {
2378   return regstack_completed
2379     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2380 }
2381 #else
2382 static inline bool
2383 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2384 {
2385   return false;
2386 }
2387 #endif
2388
2389
2390 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
2391    them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES.  */
2392
2393 static void
2394 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
2395 {
2396   rtx *pprev = &REG_NOTES (insn);
2397   rtx link = *pprev;
2398   rtx dead = NULL;
2399   rtx unused = NULL;
2400
2401   while (link)
2402     {
2403       switch (REG_NOTE_KIND (link))
2404         {
2405         case REG_DEAD:
2406           /* After reg-stack, we need to ignore any unused notes
2407              for the stack registers.  */
2408           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2409             {
2410               pprev = &XEXP (link, 1);
2411               link = *pprev;
2412             }
2413           else
2414             {
2415               rtx next = XEXP (link, 1);
2416 #ifdef REG_DEAD_DEBUGGING
2417               df_print_note ("deleting: ", insn, link);
2418 #endif
2419               XEXP (link, 1) = dead;
2420               dead = link;
2421               *pprev = link = next;
2422             }
2423           break;
2424
2425         case REG_UNUSED:
2426           /* After reg-stack, we need to ignore any unused notes
2427              for the stack registers.  */
2428           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2429             {
2430               pprev = &XEXP (link, 1);
2431               link = *pprev;
2432             }
2433           else
2434             {
2435               rtx next = XEXP (link, 1);
2436 #ifdef REG_DEAD_DEBUGGING
2437               df_print_note ("deleting: ", insn, link);
2438 #endif
2439               XEXP (link, 1) = unused;
2440               unused = link;
2441               *pprev = link = next;
2442             }
2443           break;
2444
2445         default:
2446           pprev = &XEXP (link, 1);
2447           link = *pprev;
2448           break;
2449         }
2450     }
2451
2452   *old_dead_notes = dead;
2453   *old_unused_notes = unused;
2454 }
2455
2456
2457 /* Set a NOTE_TYPE note for REG in INSN.  Try to pull it from the OLD
2458    list, otherwise create a new one.  */
2459
2460 static inline rtx
2461 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
2462 {
2463   rtx this = old;
2464   rtx prev = NULL;
2465
2466   while (this)
2467     if (XEXP (this, 0) == reg)
2468       {
2469         if (prev)
2470           XEXP (prev, 1) = XEXP (this, 1);
2471         else
2472           old = XEXP (this, 1);
2473         XEXP (this, 1) = REG_NOTES (insn);
2474         REG_NOTES (insn) = this;
2475         return old;
2476       }
2477     else
2478       {
2479         prev = this;
2480         this = XEXP (this, 1);
2481       }
2482
2483   /* Did not find the note.  */
2484   REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
2485   return old;
2486 }
2487
2488 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2489    arguments.  Return true if the register value described by MWS's
2490    mw_reg is known to be completely unused, and if mw_reg can therefore
2491    be used in a REG_UNUSED note.  */
2492
2493 static bool
2494 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2495                           bitmap live, bitmap artificial_uses)
2496 {
2497   unsigned int r;
2498
2499   /* If MWS describes a partial reference, create REG_UNUSED notes for
2500      individual hard registers.  */
2501   if (mws->flags & DF_REF_PARTIAL)
2502     return false;
2503
2504   /* Likewise if some part of the register is used.  */
2505   for (r = mws->start_regno; r <= mws->end_regno; r++)
2506     if (bitmap_bit_p (live, r)
2507         || bitmap_bit_p (artificial_uses, r))
2508       return false;
2509
2510   gcc_assert (REG_P (mws->mw_reg));
2511   return true;
2512 }
2513
2514 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2515    based on the bits in LIVE.  Do not generate notes for registers in
2516    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2517    not generated if the reg is both read and written by the
2518    instruction.
2519 */
2520
2521 static rtx
2522 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2523                             bitmap live, bitmap do_not_gen,
2524                             bitmap artificial_uses)
2525 {
2526   unsigned int r;
2527
2528 #ifdef REG_DEAD_DEBUGGING
2529   if (dump_file)
2530     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2531              mws->start_regno, mws->end_regno);
2532 #endif
2533
2534   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2535     {
2536       unsigned int regno = mws->start_regno;
2537       old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
2538
2539 #ifdef REG_DEAD_DEBUGGING
2540       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2541 #endif
2542       bitmap_set_bit (do_not_gen, regno);
2543       /* Only do this if the value is totally dead.  */
2544     }
2545   else
2546     for (r = mws->start_regno; r <= mws->end_regno; r++)
2547       {
2548         if (!bitmap_bit_p (live, r)
2549             && !bitmap_bit_p (artificial_uses, r))
2550           {
2551             old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
2552 #ifdef REG_DEAD_DEBUGGING
2553             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2554 #endif
2555           }
2556         bitmap_set_bit (do_not_gen, r);
2557       }
2558   return old;
2559 }
2560
2561
2562 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2563    arguments.  Return true if the register value described by MWS's
2564    mw_reg is known to be completely dead, and if mw_reg can therefore
2565    be used in a REG_DEAD note.  */
2566
2567 static bool
2568 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2569                         bitmap live, bitmap artificial_uses,
2570                         bitmap do_not_gen)
2571 {
2572   unsigned int r;
2573
2574   /* If MWS describes a partial reference, create REG_DEAD notes for
2575      individual hard registers.  */
2576   if (mws->flags & DF_REF_PARTIAL)
2577     return false;
2578
2579   /* Likewise if some part of the register is not dead.  */
2580   for (r = mws->start_regno; r <= mws->end_regno; r++)
2581     if (bitmap_bit_p (live, r)
2582         || bitmap_bit_p (artificial_uses, r)
2583         || bitmap_bit_p (do_not_gen, r))
2584       return false;
2585
2586   gcc_assert (REG_P (mws->mw_reg));
2587   return true;
2588 }
2589
2590 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2591    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2592    from being set if the instruction both reads and writes the
2593    register.  */
2594
2595 static rtx
2596 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
2597                           bitmap live, bitmap do_not_gen,
2598                           bitmap artificial_uses)
2599 {
2600   unsigned int r;
2601
2602 #ifdef REG_DEAD_DEBUGGING
2603   if (dump_file)
2604     {
2605       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
2606                mws->start_regno, mws->end_regno);
2607       df_print_regset (dump_file, do_not_gen);
2608       fprintf (dump_file, "  live =");
2609       df_print_regset (dump_file, live);
2610       fprintf (dump_file, "  artificial uses =");
2611       df_print_regset (dump_file, artificial_uses);
2612     }
2613 #endif
2614
2615   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
2616     {
2617       /* Add a dead note for the entire multi word register.  */
2618       old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
2619 #ifdef REG_DEAD_DEBUGGING
2620       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2621 #endif
2622     }
2623   else
2624     {
2625       for (r = mws->start_regno; r <= mws->end_regno; r++)
2626         if (!bitmap_bit_p (live, r)
2627             && !bitmap_bit_p (artificial_uses, r)
2628             && !bitmap_bit_p (do_not_gen, r))
2629           {
2630             old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
2631 #ifdef REG_DEAD_DEBUGGING
2632             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2633 #endif
2634           }
2635     }
2636   return old;
2637 }
2638
2639
2640 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
2641    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
2642
2643 static rtx
2644 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
2645                        bitmap live, bitmap artificial_uses)
2646 {
2647   unsigned int dregno = DF_REF_REGNO (def);
2648
2649 #ifdef REG_DEAD_DEBUGGING
2650   if (dump_file)
2651     {
2652       fprintf (dump_file, "  regular looking at def ");
2653       df_ref_debug (def, dump_file);
2654     }
2655 #endif
2656
2657   if (!(bitmap_bit_p (live, dregno)
2658         || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
2659         || bitmap_bit_p (artificial_uses, dregno)
2660         || df_ignore_stack_reg (dregno)))
2661     {
2662       rtx reg = (DF_REF_LOC (def))
2663                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
2664       old = df_set_note (REG_UNUSED, insn, old, reg);
2665 #ifdef REG_DEAD_DEBUGGING
2666       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
2667 #endif
2668     }
2669
2670   return old;
2671 }
2672
2673
2674 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
2675    info: lifetime, bb, and number of defs and uses for basic block
2676    BB.  The three bitvectors are scratch regs used here.  */
2677
2678 static void
2679 df_note_bb_compute (unsigned int bb_index,
2680                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
2681 {
2682   basic_block bb = BASIC_BLOCK (bb_index);
2683   rtx insn;
2684   struct df_ref **def_rec;
2685   struct df_ref **use_rec;
2686
2687   bitmap_copy (live, df_get_live_out (bb));
2688   bitmap_clear (artificial_uses);
2689
2690 #ifdef REG_DEAD_DEBUGGING
2691   if (dump_file)
2692     {
2693       fprintf (dump_file, "live at bottom ");
2694       df_print_regset (dump_file, live);
2695     }
2696 #endif
2697
2698   /* Process the artificial defs and uses at the bottom of the block
2699      to begin processing.  */
2700   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2701     {
2702       struct df_ref *def = *def_rec;
2703 #ifdef REG_DEAD_DEBUGGING
2704       if (dump_file)
2705         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
2706 #endif
2707
2708       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2709         bitmap_clear_bit (live, DF_REF_REGNO (def));
2710     }
2711
2712   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2713     {
2714       struct df_ref *use = *use_rec;
2715       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2716         {
2717           unsigned int regno = DF_REF_REGNO (use);
2718           bitmap_set_bit (live, regno);
2719
2720           /* Notes are not generated for any of the artificial registers
2721              at the bottom of the block.  */
2722           bitmap_set_bit (artificial_uses, regno);
2723         }
2724     }
2725
2726 #ifdef REG_DEAD_DEBUGGING
2727   if (dump_file)
2728     {
2729       fprintf (dump_file, "live before artificials out ");
2730       df_print_regset (dump_file, live);
2731     }
2732 #endif
2733
2734   FOR_BB_INSNS_REVERSE (bb, insn)
2735     {
2736       unsigned int uid = INSN_UID (insn);
2737       struct df_mw_hardreg **mws_rec;
2738       rtx old_dead_notes;
2739       rtx old_unused_notes;
2740
2741       if (!INSN_P (insn))
2742         continue;
2743
2744       bitmap_clear (do_not_gen);
2745       df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
2746
2747       /* Process the defs.  */
2748       if (CALL_P (insn))
2749         {
2750 #ifdef REG_DEAD_DEBUGGING
2751           if (dump_file)
2752             {
2753               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
2754               df_print_regset (dump_file, live);
2755             }
2756 #endif
2757           /* We only care about real sets for calls.  Clobbers cannot
2758              be depended on to really die.  */
2759           mws_rec = DF_INSN_UID_MWS (uid);
2760           while (*mws_rec)
2761             {
2762               struct df_mw_hardreg *mws = *mws_rec;
2763               if ((mws->type == DF_REF_REG_DEF)
2764                   && !df_ignore_stack_reg (mws->start_regno))
2765                 old_unused_notes
2766                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2767                                                 mws, live, do_not_gen,
2768                                                 artificial_uses);
2769               mws_rec++;
2770             }
2771
2772           /* All of the defs except the return value are some sort of
2773              clobber.  This code is for the return.  */
2774           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2775             {
2776               struct df_ref *def = *def_rec;
2777               unsigned int dregno = DF_REF_REGNO (def);
2778               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2779                 {
2780                   old_unused_notes
2781                     = df_create_unused_note (insn, old_unused_notes,
2782                                              def, live, artificial_uses);
2783                   bitmap_set_bit (do_not_gen, dregno);
2784                 }
2785
2786               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2787                 bitmap_clear_bit (live, dregno);
2788             }
2789         }
2790       else
2791         {
2792           /* Regular insn.  */
2793           mws_rec = DF_INSN_UID_MWS (uid);
2794           while (*mws_rec)
2795             {
2796               struct df_mw_hardreg *mws = *mws_rec;
2797               if (mws->type == DF_REF_REG_DEF)
2798                 old_unused_notes
2799                   = df_set_unused_notes_for_mw (insn, old_unused_notes,
2800                                                 mws, live, do_not_gen,
2801                                                 artificial_uses);
2802               mws_rec++;
2803             }
2804
2805           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2806             {
2807               struct df_ref *def = *def_rec;
2808               unsigned int dregno = DF_REF_REGNO (def);
2809               old_unused_notes
2810                 = df_create_unused_note (insn, old_unused_notes,
2811                                          def, live, artificial_uses);
2812
2813               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2814                 bitmap_set_bit (do_not_gen, dregno);
2815
2816               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2817                 bitmap_clear_bit (live, dregno);
2818             }
2819         }
2820
2821       /* Process the uses.  */
2822       mws_rec = DF_INSN_UID_MWS (uid);
2823       while (*mws_rec)
2824         {
2825           struct df_mw_hardreg *mws = *mws_rec;
2826           if ((mws->type != DF_REF_REG_DEF)
2827               && !df_ignore_stack_reg (mws->start_regno))
2828             old_dead_notes
2829               = df_set_dead_notes_for_mw (insn, old_dead_notes,
2830                                           mws, live, do_not_gen,
2831                                           artificial_uses);
2832           mws_rec++;
2833         }
2834
2835       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2836         {
2837           struct df_ref *use = *use_rec;
2838           unsigned int uregno = DF_REF_REGNO (use);
2839
2840 #ifdef REG_DEAD_DEBUGGING
2841           if (dump_file)
2842             {
2843               fprintf (dump_file, "  regular looking at use ");
2844               df_ref_debug (use, dump_file);
2845             }
2846 #endif
2847           if (!bitmap_bit_p (live, uregno))
2848             {
2849               if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
2850                    && (!bitmap_bit_p (do_not_gen, uregno))
2851                    && (!bitmap_bit_p (artificial_uses, uregno))
2852                    && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
2853                    && (!df_ignore_stack_reg (uregno)))
2854                 {
2855                   rtx reg = (DF_REF_LOC (use))
2856                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
2857                   old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
2858
2859 #ifdef REG_DEAD_DEBUGGING
2860                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
2861 #endif
2862                 }
2863               /* This register is now live.  */
2864               bitmap_set_bit (live, uregno);
2865             }
2866         }
2867
2868       while (old_unused_notes)
2869         {
2870           rtx next = XEXP (old_unused_notes, 1);
2871           free_EXPR_LIST_node (old_unused_notes);
2872           old_unused_notes = next;
2873         }
2874       while (old_dead_notes)
2875         {
2876           rtx next = XEXP (old_dead_notes, 1);
2877           free_EXPR_LIST_node (old_dead_notes);
2878           old_dead_notes = next;
2879         }
2880     }
2881 }
2882
2883
2884 /* Compute register info: lifetime, bb, and number of defs and uses.  */
2885 static void
2886 df_note_compute (bitmap all_blocks)
2887 {
2888   unsigned int bb_index;
2889   bitmap_iterator bi;
2890   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
2891   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
2892   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
2893
2894 #ifdef REG_DEAD_DEBUGGING
2895   if (dump_file)
2896     print_rtl_with_bb (dump_file, get_insns());
2897 #endif
2898
2899   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2900   {
2901     df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
2902   }
2903
2904   BITMAP_FREE (live);
2905   BITMAP_FREE (do_not_gen);
2906   BITMAP_FREE (artificial_uses);
2907 }
2908
2909
2910 /* Free all storage associated with the problem.  */
2911
2912 static void
2913 df_note_free (void)
2914 {
2915   free (df_note);
2916 }
2917
2918
2919 /* All of the information associated every instance of the problem.  */
2920
2921 static struct df_problem problem_NOTE =
2922 {
2923   DF_NOTE,                    /* Problem id.  */
2924   DF_NONE,                    /* Direction.  */
2925   df_note_alloc,              /* Allocate the problem specific data.  */
2926   NULL,                       /* Reset global information.  */
2927   NULL,                       /* Free basic block info.  */
2928   df_note_compute,            /* Local compute function.  */
2929   NULL,                       /* Init the solution specific data.  */
2930   NULL,                       /* Iterative solver.  */
2931   NULL,                       /* Confluence operator 0.  */
2932   NULL,                       /* Confluence operator n.  */
2933   NULL,                       /* Transfer function.  */
2934   NULL,                       /* Finalize function.  */
2935   df_note_free,               /* Free all of the problem information.  */
2936   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
2937   NULL,                       /* Debugging.  */
2938   NULL,                       /* Debugging start block.  */
2939   NULL,                       /* Debugging end block.  */
2940   NULL,                       /* Incremental solution verify start.  */
2941   NULL,                       /* Incremental solution verify end.  */
2942   &problem_LR,                /* Dependent problem.  */
2943   TV_DF_NOTE,                 /* Timing variable.  */
2944   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2945 };
2946
2947
2948 /* Create a new DATAFLOW instance and add it to an existing instance
2949    of DF.  The returned structure is what is used to get at the
2950    solution.  */
2951
2952 void
2953 df_note_add_problem (void)
2954 {
2955   df_add_problem (&problem_NOTE);
2956 }
2957
2958
2959
2960 \f
2961 /*----------------------------------------------------------------------------
2962    Functions for simulating the effects of single insns.
2963
2964    You can either simulate in the forwards direction, starting from
2965    the top of a block or the backwards direction from the end of the
2966    block.  The main difference is that if you go forwards, the uses
2967    are examined first then the defs, and if you go backwards, the defs
2968    are examined first then the uses.
2969
2970    If you start at the top of the block, use one of DF_LIVE_IN or
2971    DF_LR_IN.  If you start at the bottom of the block use one of
2972    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
2973    THEY WILL BE DESTROYED.
2974
2975 ----------------------------------------------------------------------------*/
2976
2977
2978 /* Find the set of DEFs for INSN.  */
2979
2980 void
2981 df_simulate_find_defs (rtx insn, bitmap defs)
2982 {
2983   struct df_ref **def_rec;
2984   unsigned int uid = INSN_UID (insn);
2985
2986   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2987     {
2988       struct df_ref *def = *def_rec;
2989       /* If the def is to only part of the reg, it does
2990          not kill the other defs that reach here.  */
2991       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2992         bitmap_set_bit (defs, DF_REF_REGNO (def));
2993     }
2994 }
2995
2996
2997 /* Simulate the effects of the defs of INSN on LIVE.  */
2998
2999 void
3000 df_simulate_defs (rtx insn, bitmap live)
3001 {
3002   struct df_ref **def_rec;
3003   unsigned int uid = INSN_UID (insn);
3004
3005   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3006     {
3007       struct df_ref *def = *def_rec;
3008       unsigned int dregno = DF_REF_REGNO (def);
3009
3010       /* If the def is to only part of the reg, it does
3011          not kill the other defs that reach here.  */
3012       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3013         bitmap_clear_bit (live, dregno);
3014     }
3015 }
3016
3017
3018 /* Simulate the effects of the uses of INSN on LIVE.  */
3019
3020 void
3021 df_simulate_uses (rtx insn, bitmap live)
3022 {
3023   struct df_ref **use_rec;
3024   unsigned int uid = INSN_UID (insn);
3025
3026   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3027     {
3028       struct df_ref *use = *use_rec;
3029       /* Add use to set of uses in this BB.  */
3030       bitmap_set_bit (live, DF_REF_REGNO (use));
3031     }
3032 }
3033
3034
3035 /* Add back the always live regs in BB to LIVE.  */
3036
3037 static inline void
3038 df_simulate_fixup_sets (basic_block bb, bitmap live)
3039 {
3040   /* These regs are considered always live so if they end up dying
3041      because of some def, we need to bring the back again.  */
3042   if (bb_has_eh_pred (bb))
3043     bitmap_ior_into (live, df->eh_block_artificial_uses);
3044   else
3045     bitmap_ior_into (live, df->regular_block_artificial_uses);
3046 }
3047
3048
3049 /* Apply the artificial uses and defs at the top of BB in a forwards
3050    direction.  */
3051
3052 void
3053 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3054 {
3055   struct df_ref **def_rec;
3056   struct df_ref **use_rec;
3057   int bb_index = bb->index;
3058
3059   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3060     {
3061       struct df_ref *use = *use_rec;
3062       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3063         bitmap_set_bit (live, DF_REF_REGNO (use));
3064     }
3065
3066   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3067     {
3068       struct df_ref *def = *def_rec;
3069       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3070         bitmap_clear_bit (live, DF_REF_REGNO (def));
3071     }
3072 }
3073
3074
3075 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3076
3077 void
3078 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3079 {
3080   if (! INSN_P (insn))
3081     return;
3082
3083   df_simulate_uses (insn, live);
3084   df_simulate_defs (insn, live);
3085   df_simulate_fixup_sets (bb, live);
3086 }
3087
3088
3089 /* Apply the artificial uses and defs at the end of BB in a backwards
3090    direction.  */
3091
3092 void
3093 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3094 {
3095   struct df_ref **def_rec;
3096   struct df_ref **use_rec;
3097   int bb_index = bb->index;
3098
3099   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3100     {
3101       struct df_ref *def = *def_rec;
3102       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3103         bitmap_clear_bit (live, DF_REF_REGNO (def));
3104     }
3105
3106   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3107     {
3108       struct df_ref *use = *use_rec;
3109       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3110         bitmap_set_bit (live, DF_REF_REGNO (use));
3111     }
3112 }
3113
3114
3115 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3116
3117 void
3118 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3119 {
3120   if (! INSN_P (insn))
3121     return;
3122
3123   df_simulate_defs (insn, live);
3124   df_simulate_uses (insn, live);
3125   df_simulate_fixup_sets (bb, live);
3126 }
3127
3128