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 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2841    based on the bits in LIVE.  Do not generate notes for registers in
2842    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2843    not generated if the reg is both read and written by the
2844    instruction.
2845 */
2846
2847 static void
2848 df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
2849                             bitmap live, bitmap do_not_gen,
2850                             bitmap artificial_uses)
2851 {
2852   unsigned int r;
2853
2854 #ifdef REG_DEAD_DEBUGGING
2855   if (dump_file)
2856     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2857              mws->start_regno, mws->end_regno);
2858 #endif
2859
2860   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2861     {
2862       unsigned int regno = mws->start_regno;
2863       df_set_note (REG_UNUSED, insn, mws->mw_reg);
2864
2865 #ifdef REG_DEAD_DEBUGGING
2866       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2867 #endif
2868       bitmap_set_bit (do_not_gen, regno);
2869       /* Only do this if the value is totally dead.  */
2870     }
2871   else
2872     for (r = mws->start_regno; r <= mws->end_regno; r++)
2873       {
2874         if (!bitmap_bit_p (live, r)
2875             && !bitmap_bit_p (artificial_uses, r))
2876           {
2877             df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
2878 #ifdef REG_DEAD_DEBUGGING
2879             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2880 #endif
2881           }
2882         bitmap_set_bit (do_not_gen, r);
2883       }
2884 }
2885
2886
2887 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2888    arguments.  Return true if the register value described by MWS's
2889    mw_reg is known to be completely dead, and if mw_reg can therefore
2890    be used in a REG_DEAD note.  */
2891
2892 static bool
2893 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2894                         bitmap live, bitmap artificial_uses,
2895                         bitmap do_not_gen)
2896 {
2897   unsigned int r;
2898
2899   /* If MWS describes a partial reference, create REG_DEAD notes for
2900      individual hard registers.  */
2901   if (mws->flags & DF_REF_PARTIAL)
2902     return false;
2903
2904   /* Likewise if some part of the register is not dead.  */
2905   for (r = mws->start_regno; r <= mws->end_regno; r++)
2906     if (bitmap_bit_p (live, r)
2907         || bitmap_bit_p (artificial_uses, r)
2908         || bitmap_bit_p (do_not_gen, r))
2909       return false;
2910
2911   gcc_assert (REG_P (mws->mw_reg));
2912   return true;
2913 }
2914
2915 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2916    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2917    from being set if the instruction both reads and writes the
2918    register.  */
2919
2920 static void
2921 df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
2922                           bitmap live, bitmap do_not_gen,
2923                           bitmap artificial_uses, bool *added_notes_p)
2924 {
2925   unsigned int r;
2926   bool is_debug = *added_notes_p;
2927
2928   *added_notes_p = false;
2929
2930 #ifdef REG_DEAD_DEBUGGING
2931   if (dump_file)
2932     {
2933       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
2934                mws->start_regno, mws->end_regno);
2935       df_print_regset (dump_file, do_not_gen);
2936       fprintf (dump_file, "  live =");
2937       df_print_regset (dump_file, live);
2938       fprintf (dump_file, "  artificial uses =");
2939       df_print_regset (dump_file, artificial_uses);
2940     }
2941 #endif
2942
2943   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
2944     {
2945       /* Add a dead note for the entire multi word register.  */
2946       if (is_debug)
2947         {
2948           *added_notes_p = true;
2949           return;
2950         }
2951       df_set_note (REG_DEAD, insn, mws->mw_reg);
2952 #ifdef REG_DEAD_DEBUGGING
2953       df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2954 #endif
2955     }
2956   else
2957     {
2958       for (r = mws->start_regno; r <= mws->end_regno; r++)
2959         if (!bitmap_bit_p (live, r)
2960             && !bitmap_bit_p (artificial_uses, r)
2961             && !bitmap_bit_p (do_not_gen, r))
2962           {
2963             if (is_debug)
2964               {
2965                 *added_notes_p = true;
2966                 return;
2967               }
2968             df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
2969 #ifdef REG_DEAD_DEBUGGING
2970             df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2971 #endif
2972           }
2973     }
2974   return;
2975 }
2976
2977
2978 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
2979    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
2980
2981 static void
2982 df_create_unused_note (rtx insn, df_ref def,
2983                        bitmap live, bitmap artificial_uses)
2984 {
2985   unsigned int dregno = DF_REF_REGNO (def);
2986
2987 #ifdef REG_DEAD_DEBUGGING
2988   if (dump_file)
2989     {
2990       fprintf (dump_file, "  regular looking at def ");
2991       df_ref_debug (def, dump_file);
2992     }
2993 #endif
2994
2995   if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
2996         || bitmap_bit_p (live, dregno)
2997         || bitmap_bit_p (artificial_uses, dregno)
2998         || df_ignore_stack_reg (dregno)))
2999     {
3000       rtx reg = (DF_REF_LOC (def))
3001                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3002       df_set_note (REG_UNUSED, insn, reg);
3003 #ifdef REG_DEAD_DEBUGGING
3004       df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3005 #endif
3006     }
3007
3008   return;
3009 }
3010
3011 /* Node of a linked list of uses of dead REGs in debug insns.  */
3012 struct dead_debug_use
3013 {
3014   df_ref use;
3015   struct dead_debug_use *next;
3016 };
3017
3018 /* Linked list of the above, with a bitmap of the REGs in the
3019    list.  */
3020 struct dead_debug
3021 {
3022   struct dead_debug_use *head;
3023   bitmap used;
3024   bitmap to_rescan;
3025 };
3026
3027 /* Initialize DEBUG to an empty list, and clear USED, if given.  */
3028 static inline void
3029 dead_debug_init (struct dead_debug *debug, bitmap used)
3030 {
3031   debug->head = NULL;
3032   debug->used = used;
3033   debug->to_rescan = NULL;
3034   if (used)
3035     bitmap_clear (used);
3036 }
3037
3038 /* Reset all debug insns with pending uses.  Release the bitmap in it,
3039    unless it is USED.  USED must be the same bitmap passed to
3040    dead_debug_init.  */
3041 static inline void
3042 dead_debug_finish (struct dead_debug *debug, bitmap used)
3043 {
3044   struct dead_debug_use *head;
3045   rtx insn = NULL;
3046
3047   if (debug->used != used)
3048     BITMAP_FREE (debug->used);
3049
3050   while ((head = debug->head))
3051     {
3052       insn = DF_REF_INSN (head->use);
3053       if (!head->next || DF_REF_INSN (head->next->use) != insn)
3054         {
3055           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3056           df_insn_rescan_debug_internal (insn);
3057           if (debug->to_rescan)
3058             bitmap_clear_bit (debug->to_rescan, INSN_UID (insn));
3059         }
3060       debug->head = head->next;
3061       XDELETE (head);
3062     }
3063
3064   if (debug->to_rescan)
3065     {
3066       bitmap_iterator bi;
3067       unsigned int uid;
3068
3069       EXECUTE_IF_SET_IN_BITMAP (debug->to_rescan, 0, uid, bi)
3070         {
3071           struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
3072           if (insn_info)
3073             df_insn_rescan (insn_info->insn);
3074         }
3075       BITMAP_FREE (debug->to_rescan);
3076     }
3077 }
3078
3079 /* Add USE to DEBUG.  It must be a dead reference to UREGNO in a debug
3080    insn.  Create a bitmap for DEBUG as needed.  */
3081 static inline void
3082 dead_debug_add (struct dead_debug *debug, df_ref use, unsigned int uregno)
3083 {
3084   struct dead_debug_use *newddu = XNEW (struct dead_debug_use);
3085
3086   newddu->use = use;
3087   newddu->next = debug->head;
3088   debug->head = newddu;
3089
3090   if (!debug->used)
3091     debug->used = BITMAP_ALLOC (NULL);
3092
3093   bitmap_set_bit (debug->used, uregno);
3094 }
3095
3096 /* If UREGNO is referenced by any entry in DEBUG, emit a debug insn
3097    before INSN that binds the REG to a debug temp, and replace all
3098    uses of UREGNO in DEBUG with uses of the debug temp.  INSN must be
3099    the insn where UREGNO dies.  */
3100 static inline void
3101 dead_debug_insert_before (struct dead_debug *debug, unsigned int uregno,
3102                           rtx insn)
3103 {
3104   struct dead_debug_use **tailp = &debug->head;
3105   struct dead_debug_use *cur;
3106   struct dead_debug_use *uses = NULL;
3107   struct dead_debug_use **usesp = &uses;
3108   rtx reg = NULL;
3109   rtx dval;
3110   rtx bind;
3111
3112   if (!debug->used || !bitmap_clear_bit (debug->used, uregno))
3113     return;
3114
3115   /* Move all uses of uregno from debug->head to uses, setting mode to
3116      the widest referenced mode.  */
3117   while ((cur = *tailp))
3118     {
3119       if (DF_REF_REGNO (cur->use) == uregno)
3120         {
3121           *usesp = cur;
3122           usesp = &cur->next;
3123           *tailp = cur->next;
3124           cur->next = NULL;
3125           if (!reg
3126               || (GET_MODE_BITSIZE (GET_MODE (reg))
3127                   < GET_MODE_BITSIZE (GET_MODE (*DF_REF_REAL_LOC (cur->use)))))
3128             reg = *DF_REF_REAL_LOC (cur->use);
3129         }
3130       else
3131         tailp = &(*tailp)->next;
3132     }
3133
3134   gcc_assert (reg);
3135
3136   /* Create DEBUG_EXPR (and DEBUG_EXPR_DECL).  */
3137   dval = make_debug_expr_from_rtl (reg);
3138
3139   /* Emit a debug bind insn before the insn in which reg dies.  */
3140   bind = gen_rtx_VAR_LOCATION (GET_MODE (reg),
3141                                DEBUG_EXPR_TREE_DECL (dval), reg,
3142                                VAR_INIT_STATUS_INITIALIZED);
3143
3144   bind = emit_debug_insn_before (bind, insn);
3145   df_insn_rescan (bind);
3146
3147   /* Adjust all uses.  */
3148   while ((cur = uses))
3149     {
3150       if (GET_MODE (*DF_REF_REAL_LOC (cur->use)) == GET_MODE (reg))
3151         *DF_REF_REAL_LOC (cur->use) = dval;
3152       else
3153         *DF_REF_REAL_LOC (cur->use)
3154           = gen_lowpart_SUBREG (GET_MODE (*DF_REF_REAL_LOC (cur->use)), dval);
3155       /* ??? Should we simplify subreg of subreg?  */
3156       if (debug->to_rescan == NULL)
3157         debug->to_rescan = BITMAP_ALLOC (NULL);
3158       bitmap_set_bit (debug->to_rescan, INSN_UID (DF_REF_INSN (cur->use)));
3159       uses = cur->next;
3160       XDELETE (cur);
3161     }
3162 }
3163
3164 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3165    info: lifetime, bb, and number of defs and uses for basic block
3166    BB.  The three bitvectors are scratch regs used here.  */
3167
3168 static void
3169 df_note_bb_compute (unsigned int bb_index,
3170                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3171 {
3172   basic_block bb = BASIC_BLOCK (bb_index);
3173   rtx insn;
3174   df_ref *def_rec;
3175   df_ref *use_rec;
3176   struct dead_debug debug;
3177
3178   dead_debug_init (&debug, NULL);
3179
3180   bitmap_copy (live, df_get_live_out (bb));
3181   bitmap_clear (artificial_uses);
3182
3183 #ifdef REG_DEAD_DEBUGGING
3184   if (dump_file)
3185     {
3186       fprintf (dump_file, "live at bottom ");
3187       df_print_regset (dump_file, live);
3188     }
3189 #endif
3190
3191   /* Process the artificial defs and uses at the bottom of the block
3192      to begin processing.  */
3193   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3194     {
3195       df_ref def = *def_rec;
3196 #ifdef REG_DEAD_DEBUGGING
3197       if (dump_file)
3198         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3199 #endif
3200
3201       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3202         bitmap_clear_bit (live, DF_REF_REGNO (def));
3203     }
3204
3205   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3206     {
3207       df_ref use = *use_rec;
3208       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3209         {
3210           unsigned int regno = DF_REF_REGNO (use);
3211           bitmap_set_bit (live, regno);
3212
3213           /* Notes are not generated for any of the artificial registers
3214              at the bottom of the block.  */
3215           bitmap_set_bit (artificial_uses, regno);
3216         }
3217     }
3218
3219 #ifdef REG_DEAD_DEBUGGING
3220   if (dump_file)
3221     {
3222       fprintf (dump_file, "live before artificials out ");
3223       df_print_regset (dump_file, live);
3224     }
3225 #endif
3226
3227   FOR_BB_INSNS_REVERSE (bb, insn)
3228     {
3229       unsigned int uid = INSN_UID (insn);
3230       struct df_mw_hardreg **mws_rec;
3231       int debug_insn;
3232
3233       if (!INSN_P (insn))
3234         continue;
3235
3236       debug_insn = DEBUG_INSN_P (insn);
3237
3238       bitmap_clear (do_not_gen);
3239       df_kill_notes (insn);
3240
3241       /* Process the defs.  */
3242       if (CALL_P (insn))
3243         {
3244 #ifdef REG_DEAD_DEBUGGING
3245           if (dump_file)
3246             {
3247               fprintf (dump_file, "processing call %d\n  live =", INSN_UID (insn));
3248               df_print_regset (dump_file, live);
3249             }
3250 #endif
3251           /* We only care about real sets for calls.  Clobbers cannot
3252              be depended on to really die.  */
3253           mws_rec = DF_INSN_UID_MWS (uid);
3254           while (*mws_rec)
3255             {
3256               struct df_mw_hardreg *mws = *mws_rec;
3257               if ((DF_MWS_REG_DEF_P (mws))
3258                   && !df_ignore_stack_reg (mws->start_regno))
3259               df_set_unused_notes_for_mw (insn,
3260                                           mws, live, do_not_gen,
3261                                           artificial_uses);
3262               mws_rec++;
3263             }
3264
3265           /* All of the defs except the return value are some sort of
3266              clobber.  This code is for the return.  */
3267           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3268             {
3269               df_ref def = *def_rec;
3270               unsigned int dregno = DF_REF_REGNO (def);
3271               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3272                 {
3273                   df_create_unused_note (insn,
3274                                          def, live, artificial_uses);
3275                   bitmap_set_bit (do_not_gen, dregno);
3276                 }
3277
3278               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3279                 bitmap_clear_bit (live, dregno);
3280             }
3281         }
3282       else
3283         {
3284           /* Regular insn.  */
3285           mws_rec = DF_INSN_UID_MWS (uid);
3286           while (*mws_rec)
3287             {
3288               struct df_mw_hardreg *mws = *mws_rec;
3289               if (DF_MWS_REG_DEF_P (mws))
3290                 df_set_unused_notes_for_mw (insn,
3291                                             mws, live, do_not_gen,
3292                                             artificial_uses);
3293               mws_rec++;
3294             }
3295
3296           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3297             {
3298               df_ref def = *def_rec;
3299               unsigned int dregno = DF_REF_REGNO (def);
3300               df_create_unused_note (insn,
3301                                      def, live, artificial_uses);
3302
3303               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3304                 bitmap_set_bit (do_not_gen, dregno);
3305
3306               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3307                 bitmap_clear_bit (live, dregno);
3308             }
3309         }
3310
3311       /* Process the uses.  */
3312       mws_rec = DF_INSN_UID_MWS (uid);
3313       while (*mws_rec)
3314         {
3315           struct df_mw_hardreg *mws = *mws_rec;
3316           if ((DF_MWS_REG_DEF_P (mws))
3317               && !df_ignore_stack_reg (mws->start_regno))
3318             {
3319               bool really_add_notes = debug_insn != 0;
3320
3321               df_set_dead_notes_for_mw (insn,
3322                                         mws, live, do_not_gen,
3323                                         artificial_uses,
3324                                         &really_add_notes);
3325
3326               if (really_add_notes)
3327                 debug_insn = -1;
3328             }
3329           mws_rec++;
3330         }
3331
3332       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3333         {
3334           df_ref use = *use_rec;
3335           unsigned int uregno = DF_REF_REGNO (use);
3336
3337 #ifdef REG_DEAD_DEBUGGING
3338           if (dump_file && !debug_insn)
3339             {
3340               fprintf (dump_file, "  regular looking at use ");
3341               df_ref_debug (use, dump_file);
3342             }
3343 #endif
3344           if (!bitmap_bit_p (live, uregno))
3345             {
3346               if (debug_insn)
3347                 {
3348                   if (debug_insn > 0)
3349                     {
3350                       dead_debug_add (&debug, use, uregno);
3351                       continue;
3352                     }
3353                   break;
3354                 }
3355               else
3356                 dead_debug_insert_before (&debug, uregno, insn);
3357
3358               if ( (!(DF_REF_FLAGS (use)
3359                       & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3360                    && (!bitmap_bit_p (do_not_gen, uregno))
3361                    && (!bitmap_bit_p (artificial_uses, uregno))
3362                    && (!df_ignore_stack_reg (uregno)))
3363                 {
3364                   rtx reg = (DF_REF_LOC (use))
3365                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3366                   df_set_note (REG_DEAD, insn, reg);
3367
3368 #ifdef REG_DEAD_DEBUGGING
3369                   df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3370 #endif
3371                 }
3372               /* This register is now live.  */
3373               bitmap_set_bit (live, uregno);
3374             }
3375         }
3376
3377       if (debug_insn == -1)
3378         {
3379           /* ??? We could probably do better here, replacing dead
3380              registers with their definitions.  */
3381           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3382           df_insn_rescan_debug_internal (insn);
3383         }
3384     }
3385
3386   dead_debug_finish (&debug, NULL);
3387 }
3388
3389
3390 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3391 static void
3392 df_note_compute (bitmap all_blocks)
3393 {
3394   unsigned int bb_index;
3395   bitmap_iterator bi;
3396   bitmap_head live, do_not_gen, artificial_uses;
3397
3398   bitmap_initialize (&live, &df_bitmap_obstack);
3399   bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3400   bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3401
3402 #ifdef REG_DEAD_DEBUGGING
3403   if (dump_file)
3404     print_rtl_with_bb (dump_file, get_insns());
3405 #endif
3406
3407   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3408   {
3409     df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3410   }
3411
3412   bitmap_clear (&live);
3413   bitmap_clear (&do_not_gen);
3414   bitmap_clear (&artificial_uses);
3415 }
3416
3417
3418 /* Free all storage associated with the problem.  */
3419
3420 static void
3421 df_note_free (void)
3422 {
3423   free (df_note);
3424 }
3425
3426
3427 /* All of the information associated every instance of the problem.  */
3428
3429 static struct df_problem problem_NOTE =
3430 {
3431   DF_NOTE,                    /* Problem id.  */
3432   DF_NONE,                    /* Direction.  */
3433   df_note_alloc,              /* Allocate the problem specific data.  */
3434   NULL,                       /* Reset global information.  */
3435   NULL,                       /* Free basic block info.  */
3436   df_note_compute,            /* Local compute function.  */
3437   NULL,                       /* Init the solution specific data.  */
3438   NULL,                       /* Iterative solver.  */
3439   NULL,                       /* Confluence operator 0.  */
3440   NULL,                       /* Confluence operator n.  */
3441   NULL,                       /* Transfer function.  */
3442   NULL,                       /* Finalize function.  */
3443   df_note_free,               /* Free all of the problem information.  */
3444   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3445   NULL,                       /* Debugging.  */
3446   NULL,                       /* Debugging start block.  */
3447   NULL,                       /* Debugging end block.  */
3448   NULL,                       /* Incremental solution verify start.  */
3449   NULL,                       /* Incremental solution verify end.  */
3450   &problem_LR,                /* Dependent problem.  */
3451   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
3452   TV_DF_NOTE,                 /* Timing variable.  */
3453   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3454 };
3455
3456
3457 /* Create a new DATAFLOW instance and add it to an existing instance
3458    of DF.  The returned structure is what is used to get at the
3459    solution.  */
3460
3461 void
3462 df_note_add_problem (void)
3463 {
3464   df_add_problem (&problem_NOTE);
3465 }
3466
3467
3468
3469 \f
3470 /*----------------------------------------------------------------------------
3471    Functions for simulating the effects of single insns.
3472
3473    You can either simulate in the forwards direction, starting from
3474    the top of a block or the backwards direction from the end of the
3475    block.  If you go backwards, defs are examined first to clear bits,
3476    then uses are examined to set bits.  If you go forwards, defs are
3477    examined first to set bits, then REG_DEAD and REG_UNUSED notes
3478    are examined to clear bits.  In either case, the result of examining
3479    a def can be undone (respectively by a use or a REG_UNUSED note).
3480
3481    If you start at the top of the block, use one of DF_LIVE_IN or
3482    DF_LR_IN.  If you start at the bottom of the block use one of
3483    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3484    THEY WILL BE DESTROYED.
3485 ----------------------------------------------------------------------------*/
3486
3487
3488 /* Find the set of DEFs for INSN.  */
3489
3490 void
3491 df_simulate_find_defs (rtx insn, bitmap defs)
3492 {
3493   df_ref *def_rec;
3494   unsigned int uid = INSN_UID (insn);
3495
3496   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3497     {
3498       df_ref def = *def_rec;
3499       bitmap_set_bit (defs, DF_REF_REGNO (def));
3500     }
3501 }
3502
3503 /* Find the set of real DEFs, which are not clobbers, for INSN.  */
3504
3505 void
3506 df_simulate_find_noclobber_defs (rtx insn, bitmap defs)
3507 {
3508   df_ref *def_rec;
3509   unsigned int uid = INSN_UID (insn);
3510
3511   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3512     {
3513       df_ref def = *def_rec;
3514       if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3515         bitmap_set_bit (defs, DF_REF_REGNO (def));
3516     }
3517 }
3518
3519
3520 /* Simulate the effects of the defs of INSN on LIVE.  */
3521
3522 void
3523 df_simulate_defs (rtx insn, bitmap live)
3524 {
3525   df_ref *def_rec;
3526   unsigned int uid = INSN_UID (insn);
3527
3528   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3529     {
3530       df_ref def = *def_rec;
3531       unsigned int dregno = DF_REF_REGNO (def);
3532
3533       /* If the def is to only part of the reg, it does
3534          not kill the other defs that reach here.  */
3535       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3536         bitmap_clear_bit (live, dregno);
3537     }
3538 }
3539
3540
3541 /* Simulate the effects of the uses of INSN on LIVE.  */
3542
3543 void
3544 df_simulate_uses (rtx insn, bitmap live)
3545 {
3546   df_ref *use_rec;
3547   unsigned int uid = INSN_UID (insn);
3548
3549   if (DEBUG_INSN_P (insn))
3550     return;
3551
3552   for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3553     {
3554       df_ref use = *use_rec;
3555       /* Add use to set of uses in this BB.  */
3556       bitmap_set_bit (live, DF_REF_REGNO (use));
3557     }
3558 }
3559
3560
3561 /* Add back the always live regs in BB to LIVE.  */
3562
3563 static inline void
3564 df_simulate_fixup_sets (basic_block bb, bitmap live)
3565 {
3566   /* These regs are considered always live so if they end up dying
3567      because of some def, we need to bring the back again.  */
3568   if (bb_has_eh_pred (bb))
3569     bitmap_ior_into (live, &df->eh_block_artificial_uses);
3570   else
3571     bitmap_ior_into (live, &df->regular_block_artificial_uses);
3572 }
3573
3574
3575 /*----------------------------------------------------------------------------
3576    The following three functions are used only for BACKWARDS scanning:
3577    i.e. they process the defs before the uses.
3578
3579    df_simulate_initialize_backwards should be called first with a
3580    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3581    df_simulate_one_insn_backwards should be called for each insn in
3582    the block, starting with the last one.  Finally,
3583    df_simulate_finalize_backwards can be called to get a new value
3584    of the sets at the top of the block (this is rarely used).
3585    ----------------------------------------------------------------------------*/
3586
3587 /* Apply the artificial uses and defs at the end of BB in a backwards
3588    direction.  */
3589
3590 void
3591 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3592 {
3593   df_ref *def_rec;
3594   df_ref *use_rec;
3595   int bb_index = bb->index;
3596
3597   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3598     {
3599       df_ref def = *def_rec;
3600       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3601         bitmap_clear_bit (live, DF_REF_REGNO (def));
3602     }
3603
3604   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3605     {
3606       df_ref use = *use_rec;
3607       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3608         bitmap_set_bit (live, DF_REF_REGNO (use));
3609     }
3610 }
3611
3612
3613 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3614
3615 void
3616 df_simulate_one_insn_backwards (basic_block bb, rtx insn, bitmap live)
3617 {
3618   if (!NONDEBUG_INSN_P (insn))
3619     return;
3620
3621   df_simulate_defs (insn, live);
3622   df_simulate_uses (insn, live);
3623   df_simulate_fixup_sets (bb, live);
3624 }
3625
3626
3627 /* Apply the artificial uses and defs at the top of BB in a backwards
3628    direction.  */
3629
3630 void
3631 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3632 {
3633   df_ref *def_rec;
3634 #ifdef EH_USES
3635   df_ref *use_rec;
3636 #endif
3637   int bb_index = bb->index;
3638
3639   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3640     {
3641       df_ref def = *def_rec;
3642       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3643         bitmap_clear_bit (live, DF_REF_REGNO (def));
3644     }
3645
3646 #ifdef EH_USES
3647   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3648     {
3649       df_ref use = *use_rec;
3650       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3651         bitmap_set_bit (live, DF_REF_REGNO (use));
3652     }
3653 #endif
3654 }
3655 /*----------------------------------------------------------------------------
3656    The following three functions are used only for FORWARDS scanning:
3657    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3658    Thus it is important to add the DF_NOTES problem to the stack of
3659    problems computed before using these functions.
3660
3661    df_simulate_initialize_forwards should be called first with a
3662    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3663    df_simulate_one_insn_forwards should be called for each insn in
3664    the block, starting with the first one.
3665    ----------------------------------------------------------------------------*/
3666
3667 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3668    DF_LR_IN for basic block BB, for forward scanning by marking artificial
3669    defs live.  */
3670
3671 void
3672 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3673 {
3674   df_ref *def_rec;
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_set_bit (live, DF_REF_REGNO (def));
3682     }
3683 }
3684
3685 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3686
3687 void
3688 df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
3689 {
3690   rtx link;
3691   if (! INSN_P (insn))
3692     return;
3693
3694   /* Make sure that DF_NOTE really is an active df problem.  */
3695   gcc_assert (df_note);
3696
3697   /* Note that this is the opposite as how the problem is defined, because
3698      in the LR problem defs _kill_ liveness.  However, they do so backwards,
3699      while here the scan is performed forwards!  So, first assume that the
3700      def is live, and if this is not true REG_UNUSED notes will rectify the
3701      situation.  */
3702   df_simulate_find_noclobber_defs (insn, live);
3703
3704   /* Clear all of the registers that go dead.  */
3705   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3706     {
3707       switch (REG_NOTE_KIND (link))
3708         {
3709         case REG_DEAD:
3710         case REG_UNUSED:
3711           {
3712             rtx reg = XEXP (link, 0);
3713             int regno = REGNO (reg);
3714             if (regno < FIRST_PSEUDO_REGISTER)
3715               {
3716                 int n = hard_regno_nregs[regno][GET_MODE (reg)];
3717                 while (--n >= 0)
3718                   bitmap_clear_bit (live, regno + n);
3719               }
3720             else
3721               bitmap_clear_bit (live, regno);
3722           }
3723           break;
3724         default:
3725           break;
3726         }
3727     }
3728   df_simulate_fixup_sets (bb, live);
3729 }
3730
3731
3732 \f
3733 /*----------------------------------------------------------------------------
3734    MULTIPLE DEFINITIONS
3735
3736    Find the locations in the function reached by multiple definition sites
3737    for a live pseudo.  In and out bitvectors are built for each basic
3738    block.  They are restricted for efficiency to live registers.
3739
3740    The gen and kill sets for the problem are obvious.  Together they
3741    include all defined registers in a basic block; the gen set includes
3742    registers where a partial or conditional or may-clobber definition is
3743    last in the BB, while the kill set includes registers with a complete
3744    definition coming last.  However, the computation of the dataflow
3745    itself is interesting.
3746
3747    The idea behind it comes from SSA form's iterated dominance frontier
3748    criterion for inserting PHI functions.  Just like in that case, we can use
3749    the dominance frontier to find places where multiple definitions meet;
3750    a register X defined in a basic block BB1 has multiple definitions in
3751    basic blocks in BB1's dominance frontier.
3752
3753    So, the in-set of a basic block BB2 is not just the union of the
3754    out-sets of BB2's predecessors, but includes some more bits that come
3755    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3756    the previous paragraph).  I called this set the init-set of BB2.
3757
3758       (Note: I actually use the kill-set only to build the init-set.
3759       gen bits are anyway propagated from BB1 to BB2 by dataflow).
3760
3761     For example, if you have
3762
3763        BB1 : r10 = 0
3764              r11 = 0
3765              if <...> goto BB2 else goto BB3;
3766
3767        BB2 : r10 = 1
3768              r12 = 1
3769              goto BB3;
3770
3771        BB3 :
3772
3773     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3774     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
3775     not need to iterate the dominance frontier, because we do not insert
3776     anything like PHI functions there!  Instead, dataflow will take care of
3777     propagating the information to BB3's successors.
3778    ---------------------------------------------------------------------------*/
3779
3780 /* Private data used to verify the solution for this problem.  */
3781 struct df_md_problem_data
3782 {
3783   /* An obstack for the bitmaps we need for this problem.  */
3784   bitmap_obstack md_bitmaps;
3785 };
3786
3787 /* Scratch var used by transfer functions.  This is used to do md analysis
3788    only for live registers.  */
3789 static bitmap_head df_md_scratch;
3790
3791
3792 static void
3793 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3794                     void *vbb_info)
3795 {
3796   struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
3797   if (bb_info)
3798     {
3799       bitmap_clear (&bb_info->kill);
3800       bitmap_clear (&bb_info->gen);
3801       bitmap_clear (&bb_info->init);
3802       bitmap_clear (&bb_info->in);
3803       bitmap_clear (&bb_info->out);
3804     }
3805 }
3806
3807
3808 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3809    not touched unless the block is new.  */
3810
3811 static void
3812 df_md_alloc (bitmap all_blocks)
3813 {
3814   unsigned int bb_index;
3815   bitmap_iterator bi;
3816   struct df_md_problem_data *problem_data;
3817
3818   df_grow_bb_info (df_md);
3819   if (df_md->problem_data)
3820     problem_data = (struct df_md_problem_data *) df_md->problem_data;
3821   else
3822     {
3823       problem_data = XNEW (struct df_md_problem_data);
3824       df_md->problem_data = problem_data;
3825       bitmap_obstack_initialize (&problem_data->md_bitmaps);
3826     }
3827   bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
3828
3829   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3830     {
3831       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
3832       /* When bitmaps are already initialized, just clear them.  */
3833       if (bb_info->init.obstack)
3834         {
3835           bitmap_clear (&bb_info->init);
3836           bitmap_clear (&bb_info->gen);
3837           bitmap_clear (&bb_info->kill);
3838           bitmap_clear (&bb_info->in);
3839           bitmap_clear (&bb_info->out);
3840         }
3841       else
3842         {
3843           bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
3844           bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
3845           bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
3846           bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
3847           bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
3848         }
3849     }
3850
3851   df_md->optional_p = true;
3852 }
3853
3854 /* Add the effect of the top artificial defs of BB to the multiple definitions
3855    bitmap LOCAL_MD.  */
3856
3857 void
3858 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
3859 {
3860   int bb_index = bb->index;
3861   df_ref *def_rec;
3862   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3863     {
3864       df_ref def = *def_rec;
3865       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3866         {
3867           unsigned int dregno = DF_REF_REGNO (def);
3868           if (DF_REF_FLAGS (def)
3869               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
3870             bitmap_set_bit (local_md, dregno);
3871           else
3872             bitmap_clear_bit (local_md, dregno);
3873         }
3874     }
3875 }
3876
3877
3878 /* Add the effect of the defs of INSN to the reaching definitions bitmap
3879    LOCAL_MD.  */
3880
3881 void
3882 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
3883                         bitmap local_md)
3884 {
3885   unsigned uid = INSN_UID (insn);
3886   df_ref *def_rec;
3887
3888   for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3889     {
3890       df_ref def = *def_rec;
3891       unsigned int dregno = DF_REF_REGNO (def);
3892       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
3893           || (dregno >= FIRST_PSEUDO_REGISTER))
3894         {
3895           if (DF_REF_FLAGS (def)
3896               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
3897            bitmap_set_bit (local_md, DF_REF_ID (def));
3898          else
3899            bitmap_clear_bit (local_md, DF_REF_ID (def));
3900         }
3901     }
3902 }
3903
3904 static void
3905 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
3906                                     df_ref *def_rec,
3907                                     int top_flag)
3908 {
3909   df_ref def;
3910   bitmap_clear (&seen_in_insn);
3911
3912   while ((def = *def_rec++) != NULL)
3913     {
3914       unsigned int dregno = DF_REF_REGNO (def);
3915       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
3916             || (dregno >= FIRST_PSEUDO_REGISTER))
3917           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
3918         {
3919           if (!bitmap_bit_p (&seen_in_insn, dregno))
3920             {
3921               if (DF_REF_FLAGS (def)
3922                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
3923                 {
3924                   bitmap_set_bit (&bb_info->gen, dregno);
3925                   bitmap_clear_bit (&bb_info->kill, dregno);
3926                 }
3927               else
3928                 {
3929                   /* When we find a clobber and a regular def,
3930                      make sure the regular def wins.  */
3931                   bitmap_set_bit (&seen_in_insn, dregno);
3932                   bitmap_set_bit (&bb_info->kill, dregno);
3933                   bitmap_clear_bit (&bb_info->gen, dregno);
3934                 }
3935             }
3936         }
3937     }
3938 }
3939
3940
3941 /* Compute local multiple def info for basic block BB.  */
3942
3943 static void
3944 df_md_bb_local_compute (unsigned int bb_index)
3945 {
3946   basic_block bb = BASIC_BLOCK (bb_index);
3947   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
3948   rtx insn;
3949
3950   /* Artificials are only hard regs.  */
3951   if (!(df->changeable_flags & DF_NO_HARD_REGS))
3952     df_md_bb_local_compute_process_def (bb_info,
3953                                         df_get_artificial_defs (bb_index),
3954                                         DF_REF_AT_TOP);
3955
3956   FOR_BB_INSNS (bb, insn)
3957     {
3958       unsigned int uid = INSN_UID (insn);
3959       if (!INSN_P (insn))
3960         continue;
3961
3962       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
3963     }
3964
3965   if (!(df->changeable_flags & DF_NO_HARD_REGS))
3966     df_md_bb_local_compute_process_def (bb_info,
3967                                         df_get_artificial_defs (bb_index),
3968                                         0);
3969 }
3970
3971 /* Compute local reaching def info for each basic block within BLOCKS.  */
3972
3973 static void
3974 df_md_local_compute (bitmap all_blocks)
3975 {
3976   unsigned int bb_index, df_bb_index;
3977   bitmap_iterator bi1, bi2;
3978   basic_block bb;
3979   bitmap_head *frontiers;
3980
3981   bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
3982
3983   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
3984     {
3985       df_md_bb_local_compute (bb_index);
3986     }
3987
3988   bitmap_clear (&seen_in_insn);
3989
3990   frontiers = XNEWVEC (bitmap_head, last_basic_block);
3991   FOR_ALL_BB (bb)
3992     bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
3993
3994   compute_dominance_frontiers (frontiers);
3995
3996   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
3997   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
3998     {
3999       bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4000       EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4001         {
4002           basic_block bb = BASIC_BLOCK (df_bb_index);
4003           if (bitmap_bit_p (all_blocks, df_bb_index))
4004             bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4005                                  df_get_live_in (bb));
4006         }
4007     }
4008
4009   FOR_ALL_BB (bb)
4010     bitmap_clear (&frontiers[bb->index]);
4011   free (frontiers);
4012 }
4013
4014
4015 /* Reset the global solution for recalculation.  */
4016
4017 static void
4018 df_md_reset (bitmap all_blocks)
4019 {
4020   unsigned int bb_index;
4021   bitmap_iterator bi;
4022
4023   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4024     {
4025       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4026       gcc_assert (bb_info);
4027       bitmap_clear (&bb_info->in);
4028       bitmap_clear (&bb_info->out);
4029     }
4030 }
4031
4032 static bool
4033 df_md_transfer_function (int bb_index)
4034 {
4035   basic_block bb = BASIC_BLOCK (bb_index);
4036   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4037   bitmap in = &bb_info->in;
4038   bitmap out = &bb_info->out;
4039   bitmap gen = &bb_info->gen;
4040   bitmap kill = &bb_info->kill;
4041
4042   /* We need to use a scratch set here so that the value returned from this
4043      function invocation properly reflects whether the sets changed in a
4044      significant way; i.e. not just because the live set was anded in.  */
4045   bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4046
4047   /* Multiple definitions of a register are not relevant if it is not
4048      live.  Thus we trim the result to the places where it is live.  */
4049   bitmap_and_into (in, df_get_live_in (bb));
4050
4051   return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4052 }
4053
4054 /* Initialize the solution bit vectors for problem.  */
4055
4056 static void
4057 df_md_init (bitmap all_blocks)
4058 {
4059   unsigned int bb_index;
4060   bitmap_iterator bi;
4061
4062   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4063     {
4064       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4065
4066       bitmap_copy (&bb_info->in, &bb_info->init);
4067       df_md_transfer_function (bb_index);
4068     }
4069 }
4070
4071 static void
4072 df_md_confluence_0 (basic_block bb)
4073 {
4074   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4075   bitmap_copy (&bb_info->in, &bb_info->init);
4076 }
4077
4078 /* In of target gets or of out of source.  */
4079
4080 static bool
4081 df_md_confluence_n (edge e)
4082 {
4083   bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4084   bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4085
4086   if (e->flags & EDGE_FAKE)
4087     return false;
4088
4089   if (e->flags & EDGE_EH)
4090     return bitmap_ior_and_compl_into (op1, op2,
4091                                       regs_invalidated_by_call_regset);
4092   else
4093     return bitmap_ior_into (op1, op2);
4094 }
4095
4096 /* Free all storage associated with the problem.  */
4097
4098 static void
4099 df_md_free (void)
4100 {
4101   struct df_md_problem_data *problem_data
4102     = (struct df_md_problem_data *) df_md->problem_data;
4103
4104   bitmap_obstack_release (&problem_data->md_bitmaps);
4105   free (problem_data);
4106   df_md->problem_data = NULL;
4107
4108   df_md->block_info_size = 0;
4109   free (df_md->block_info);
4110   df_md->block_info = NULL;
4111   free (df_md);
4112 }
4113
4114
4115 /* Debugging info at top of bb.  */
4116
4117 static void
4118 df_md_top_dump (basic_block bb, FILE *file)
4119 {
4120   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4121   if (!bb_info)
4122     return;
4123
4124   fprintf (file, ";; md  in  \t");
4125   df_print_regset (file, &bb_info->in);
4126   fprintf (file, ";; md  init  \t");
4127   df_print_regset (file, &bb_info->init);
4128   fprintf (file, ";; md  gen \t");
4129   df_print_regset (file, &bb_info->gen);
4130   fprintf (file, ";; md  kill \t");
4131   df_print_regset (file, &bb_info->kill);
4132 }
4133
4134 /* Debugging info at bottom of bb.  */
4135
4136 static void
4137 df_md_bottom_dump (basic_block bb, FILE *file)
4138 {
4139   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4140   if (!bb_info)
4141     return;
4142
4143   fprintf (file, ";; md  out \t");
4144   df_print_regset (file, &bb_info->out);
4145 }
4146
4147 static struct df_problem problem_MD =
4148 {
4149   DF_MD,                      /* Problem id.  */
4150   DF_FORWARD,                 /* Direction.  */
4151   df_md_alloc,                /* Allocate the problem specific data.  */
4152   df_md_reset,                /* Reset global information.  */
4153   df_md_free_bb_info,         /* Free basic block info.  */
4154   df_md_local_compute,        /* Local compute function.  */
4155   df_md_init,                 /* Init the solution specific data.  */
4156   df_worklist_dataflow,       /* Worklist solver.  */
4157   df_md_confluence_0,         /* Confluence operator 0.  */
4158   df_md_confluence_n,         /* Confluence operator n.  */
4159   df_md_transfer_function,    /* Transfer function.  */
4160   NULL,                       /* Finalize function.  */
4161   df_md_free,                 /* Free all of the problem information.  */
4162   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4163   NULL,                       /* Debugging.  */
4164   df_md_top_dump,             /* Debugging start block.  */
4165   df_md_bottom_dump,          /* Debugging end block.  */
4166   NULL,                       /* Incremental solution verify start.  */
4167   NULL,                       /* Incremental solution verify end.  */
4168   NULL,                       /* Dependent problem.  */
4169   sizeof (struct df_md_bb_info),/* Size of entry of block_info array.  */
4170   TV_DF_MD,                   /* Timing variable.  */
4171   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4172 };
4173
4174 /* Create a new MD instance and add it to the existing instance
4175    of DF.  */
4176
4177 void
4178 df_md_add_problem (void)
4179 {
4180   df_add_problem (&problem_MD);
4181 }
4182
4183
4184