gcc/df-problems.c

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