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