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