contrib/gcc-5.0/gcc/df-problems.c

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