gcc/df-problems.c

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