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