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 MAY-INITIALIZED REGISTERS.
1327
1328    This problem first computes the IN and OUT bitvectors for the
1329    may-initialized registers problems, which is a forward problem.
1330    It gives the set of registers for which we MAY have an available
1331    definition, i.e. for which there is an available definition on
1332    at least one path from the entry block to the entry/exit of a
1333    basic block.  Sets generate a definition, while clobbers kill
1334    a definition.
1335
1336    In and out bitvectors are built for each basic block and are indexed by
1337    regnum (see df.h for details).  In and out bitvectors in struct
1338    df_live_bb_info actually refers to the may-initialized problem;
1339
1340    Then, the in and out sets for the LIVE problem itself are computed.
1341    These are the logical AND of the IN and OUT sets from the LR problem
1342    and the may-initialized problem.
1343 ----------------------------------------------------------------------------*/
1344
1345 /* Private data used to verify the solution for this problem.  */
1346 struct df_live_problem_data
1347 {
1348   bitmap_head *in;
1349   bitmap_head *out;
1350   /* An obstack for the bitmaps we need for this problem.  */
1351   bitmap_obstack live_bitmaps;
1352 };
1353
1354 /* Scratch var used by transfer functions.  This is used to implement
1355    an optimization to reduce the amount of space used to compute the
1356    combined lr and live analysis.  */
1357 static bitmap_head df_live_scratch;
1358
1359
1360 /* Free basic block info.  */
1361
1362 static void
1363 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1364                     void *vbb_info)
1365 {
1366   struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1367   if (bb_info)
1368     {
1369       bitmap_clear (&bb_info->gen);
1370       bitmap_clear (&bb_info->kill);
1371       bitmap_clear (&bb_info->in);
1372       bitmap_clear (&bb_info->out);
1373     }
1374 }
1375
1376
1377 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1378    not touched unless the block is new.  */
1379
1380 static void
1381 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1382 {
1383   unsigned int bb_index;
1384   bitmap_iterator bi;
1385   struct df_live_problem_data *problem_data;
1386
1387   if (df_live->problem_data)
1388     problem_data = (struct df_live_problem_data *) df_live->problem_data;
1389   else
1390     {
1391       problem_data = XNEW (struct df_live_problem_data);
1392       df_live->problem_data = problem_data;
1393
1394       problem_data->out = NULL;
1395       problem_data->in = NULL;
1396       bitmap_obstack_initialize (&problem_data->live_bitmaps);
1397       bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1398     }
1399
1400   df_grow_bb_info (df_live);
1401
1402   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1403     {
1404       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1405
1406       /* When bitmaps are already initialized, just clear them.  */
1407       if (bb_info->kill.obstack)
1408         {
1409           bitmap_clear (&bb_info->kill);
1410           bitmap_clear (&bb_info->gen);
1411         }
1412       else
1413         {
1414           bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1415           bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1416           bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1417           bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1418         }
1419     }
1420   df_live->optional_p = (optimize <= 1);
1421 }
1422
1423
1424 /* Reset the global solution for recalculation.  */
1425
1426 static void
1427 df_live_reset (bitmap all_blocks)
1428 {
1429   unsigned int bb_index;
1430   bitmap_iterator bi;
1431
1432   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1433     {
1434       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1435       gcc_assert (bb_info);
1436       bitmap_clear (&bb_info->in);
1437       bitmap_clear (&bb_info->out);
1438     }
1439 }
1440
1441
1442 /* Compute local uninitialized register info for basic block BB.  */
1443
1444 static void
1445 df_live_bb_local_compute (unsigned int bb_index)
1446 {
1447   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1448   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1449   rtx_insn *insn;
1450   df_ref def;
1451   int luid = 0;
1452
1453   FOR_BB_INSNS (bb, insn)
1454     {
1455       unsigned int uid = INSN_UID (insn);
1456       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1457
1458       /* Inserting labels does not always trigger the incremental
1459          rescanning.  */
1460       if (!insn_info)
1461         {
1462           gcc_assert (!INSN_P (insn));
1463           insn_info = df_insn_create_insn_record (insn);
1464         }
1465
1466       DF_INSN_INFO_LUID (insn_info) = luid;
1467       if (!INSN_P (insn))
1468         continue;
1469
1470       luid++;
1471       FOR_EACH_INSN_INFO_DEF (def, insn_info)
1472         {
1473           unsigned int regno = DF_REF_REGNO (def);
1474
1475           if (DF_REF_FLAGS_IS_SET (def,
1476                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1477             /* All partial or conditional def
1478                seen are included in the gen set. */
1479             bitmap_set_bit (&bb_info->gen, regno);
1480           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1481             /* Only must clobbers for the entire reg destroy the
1482                value.  */
1483             bitmap_set_bit (&bb_info->kill, regno);
1484           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1485             bitmap_set_bit (&bb_info->gen, regno);
1486         }
1487     }
1488
1489   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1490     bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1491 }
1492
1493
1494 /* Compute local uninitialized register info.  */
1495
1496 static void
1497 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1498 {
1499   unsigned int bb_index;
1500   bitmap_iterator bi;
1501
1502   df_grow_insn_info ();
1503
1504   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1505                             0, bb_index, bi)
1506     {
1507       df_live_bb_local_compute (bb_index);
1508     }
1509
1510   bitmap_clear (df_live->out_of_date_transfer_functions);
1511 }
1512
1513
1514 /* Initialize the solution vectors.  */
1515
1516 static void
1517 df_live_init (bitmap all_blocks)
1518 {
1519   unsigned int bb_index;
1520   bitmap_iterator bi;
1521
1522   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1523     {
1524       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1525       struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1526
1527       /* No register may reach a location where it is not used.  Thus
1528          we trim the rr result to the places where it is used.  */
1529       bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1530       bitmap_clear (&bb_info->in);
1531     }
1532 }
1533
1534 /* Forward confluence function that ignores fake edges.  */
1535
1536 static bool
1537 df_live_confluence_n (edge e)
1538 {
1539   bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1540   bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1541
1542   if (e->flags & EDGE_FAKE)
1543     return false;
1544
1545   return bitmap_ior_into (op1, op2);
1546 }
1547
1548
1549 /* Transfer function for the forwards may-initialized problem.  */
1550
1551 static bool
1552 df_live_transfer_function (int bb_index)
1553 {
1554   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1555   struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1556   bitmap in = &bb_info->in;
1557   bitmap out = &bb_info->out;
1558   bitmap gen = &bb_info->gen;
1559   bitmap kill = &bb_info->kill;
1560
1561   /* We need to use a scratch set here so that the value returned from this
1562      function invocation properly reflects whether the sets changed in a
1563      significant way; i.e. not just because the lr set was anded in.  */
1564   bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1565   /* No register may reach a location where it is not used.  Thus
1566      we trim the rr result to the places where it is used.  */
1567   bitmap_and_into (in, &bb_lr_info->in);
1568
1569   return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1570 }
1571
1572
1573 /* And the LR info with the may-initialized registers to produce the LIVE info.  */
1574
1575 static void
1576 df_live_finalize (bitmap all_blocks)
1577 {
1578
1579   if (df_live->solutions_dirty)
1580     {
1581       bitmap_iterator bi;
1582       unsigned int bb_index;
1583
1584       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1585         {
1586           struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1587           struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1588
1589           /* No register may reach a location where it is not used.  Thus
1590              we trim the rr result to the places where it is used.  */
1591           bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1592           bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1593         }
1594
1595       df_live->solutions_dirty = false;
1596     }
1597 }
1598
1599
1600 /* Free all storage associated with the problem.  */
1601
1602 static void
1603 df_live_free (void)
1604 {
1605   struct df_live_problem_data *problem_data
1606     = (struct df_live_problem_data *) df_live->problem_data;
1607   if (df_live->block_info)
1608     {
1609       df_live->block_info_size = 0;
1610       free (df_live->block_info);
1611       df_live->block_info = NULL;
1612       bitmap_clear (&df_live_scratch);
1613       bitmap_obstack_release (&problem_data->live_bitmaps);
1614       free (problem_data);
1615       df_live->problem_data = NULL;
1616     }
1617   BITMAP_FREE (df_live->out_of_date_transfer_functions);
1618   free (df_live);
1619 }
1620
1621
1622 /* Debugging info at top of bb.  */
1623
1624 static void
1625 df_live_top_dump (basic_block bb, FILE *file)
1626 {
1627   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1628   struct df_live_problem_data *problem_data;
1629
1630   if (!bb_info)
1631     return;
1632
1633   fprintf (file, ";; live  in  \t");
1634   df_print_regset (file, &bb_info->in);
1635   if (df_live->problem_data)
1636     {
1637       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1638       if (problem_data->in)
1639         {
1640           fprintf (file, ";;  old in  \t");
1641           df_print_regset (file, &problem_data->in[bb->index]);
1642         }
1643     }
1644   fprintf (file, ";; live  gen \t");
1645   df_print_regset (file, &bb_info->gen);
1646   fprintf (file, ";; live  kill\t");
1647   df_print_regset (file, &bb_info->kill);
1648 }
1649
1650
1651 /* Debugging info at bottom of bb.  */
1652
1653 static void
1654 df_live_bottom_dump (basic_block bb, FILE *file)
1655 {
1656   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1657   struct df_live_problem_data *problem_data;
1658
1659   if (!bb_info)
1660     return;
1661
1662   fprintf (file, ";; live  out \t");
1663   df_print_regset (file, &bb_info->out);
1664   if (df_live->problem_data)
1665     {
1666       problem_data = (struct df_live_problem_data *)df_live->problem_data;
1667       if (problem_data->out)
1668         {
1669           fprintf (file, ";;  old out  \t");
1670           df_print_regset (file, &problem_data->out[bb->index]);
1671         }
1672     }
1673 }
1674
1675
1676 /* Build the datastructure to verify that the solution to the dataflow
1677    equations is not dirty.  */
1678
1679 static void
1680 df_live_verify_solution_start (void)
1681 {
1682   basic_block bb;
1683   struct df_live_problem_data *problem_data;
1684   if (df_live->solutions_dirty)
1685     return;
1686
1687   /* Set it true so that the solution is recomputed.  */
1688   df_live->solutions_dirty = true;
1689
1690   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1691   problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1692   problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1693
1694   FOR_ALL_BB_FN (bb, cfun)
1695     {
1696       bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1697       bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1698       bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1699       bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1700     }
1701 }
1702
1703
1704 /* Compare the saved datastructure and the new solution to the dataflow
1705    equations.  */
1706
1707 static void
1708 df_live_verify_solution_end (void)
1709 {
1710   struct df_live_problem_data *problem_data;
1711   basic_block bb;
1712
1713   problem_data = (struct df_live_problem_data *)df_live->problem_data;
1714   if (!problem_data->out)
1715     return;
1716
1717   FOR_ALL_BB_FN (bb, cfun)
1718     {
1719       if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1720           || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1721         {
1722           /*df_dump (stderr);*/
1723           gcc_unreachable ();
1724         }
1725     }
1726
1727   /* Cannot delete them immediately because you may want to dump them
1728      if the comparison fails.  */
1729   FOR_ALL_BB_FN (bb, cfun)
1730     {
1731       bitmap_clear (&problem_data->in[bb->index]);
1732       bitmap_clear (&problem_data->out[bb->index]);
1733     }
1734
1735   free (problem_data->in);
1736   free (problem_data->out);
1737   free (problem_data);
1738   df_live->problem_data = NULL;
1739 }
1740
1741
1742 /* All of the information associated with every instance of the problem.  */
1743
1744 static struct df_problem problem_LIVE =
1745 {
1746   DF_LIVE,                      /* Problem id.  */
1747   DF_FORWARD,                   /* Direction.  */
1748   df_live_alloc,                /* Allocate the problem specific data.  */
1749   df_live_reset,                /* Reset global information.  */
1750   df_live_free_bb_info,         /* Free basic block info.  */
1751   df_live_local_compute,        /* Local compute function.  */
1752   df_live_init,                 /* Init the solution specific data.  */
1753   df_worklist_dataflow,         /* Worklist solver.  */
1754   NULL,                         /* Confluence operator 0.  */
1755   df_live_confluence_n,         /* Confluence operator n.  */
1756   df_live_transfer_function,    /* Transfer function.  */
1757   df_live_finalize,             /* Finalize function.  */
1758   df_live_free,                 /* Free all of the problem information.  */
1759   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
1760   NULL,                         /* Debugging.  */
1761   df_live_top_dump,             /* Debugging start block.  */
1762   df_live_bottom_dump,          /* Debugging end block.  */
1763   NULL,                         /* Debugging start insn.  */
1764   NULL,                         /* Debugging end insn.  */
1765   df_live_verify_solution_start,/* Incremental solution verify start.  */
1766   df_live_verify_solution_end,  /* Incremental solution verify end.  */
1767   &problem_LR,                  /* Dependent problem.  */
1768   sizeof (struct df_live_bb_info),/* Size of entry of block_info array.  */
1769   TV_DF_LIVE,                   /* Timing variable.  */
1770   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
1771 };
1772
1773
1774 /* Create a new DATAFLOW instance and add it to an existing instance
1775    of DF.  The returned structure is what is used to get at the
1776    solution.  */
1777
1778 void
1779 df_live_add_problem (void)
1780 {
1781   df_add_problem (&problem_LIVE);
1782   /* These will be initialized when df_scan_blocks processes each
1783      block.  */
1784   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1785 }
1786
1787
1788 /* Set all of the blocks as dirty.  This needs to be done if this
1789    problem is added after all of the insns have been scanned.  */
1790
1791 void
1792 df_live_set_all_dirty (void)
1793 {
1794   basic_block bb;
1795   FOR_ALL_BB_FN (bb, cfun)
1796     bitmap_set_bit (df_live->out_of_date_transfer_functions,
1797                     bb->index);
1798 }
1799
1800
1801 /* Verify that all of the lr related info is consistent and
1802    correct.  */
1803
1804 void
1805 df_live_verify_transfer_functions (void)
1806 {
1807   basic_block bb;
1808   bitmap_head saved_gen;
1809   bitmap_head saved_kill;
1810   bitmap_head all_blocks;
1811
1812   if (!df)
1813     return;
1814
1815   bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1816   bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1817   bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1818
1819   df_grow_insn_info ();
1820
1821   FOR_ALL_BB_FN (bb, cfun)
1822     {
1823       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1824       bitmap_set_bit (&all_blocks, bb->index);
1825
1826       if (bb_info)
1827         {
1828           /* Make a copy of the transfer functions and then compute
1829              new ones to see if the transfer functions have
1830              changed.  */
1831           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1832                              bb->index))
1833             {
1834               bitmap_copy (&saved_gen, &bb_info->gen);
1835               bitmap_copy (&saved_kill, &bb_info->kill);
1836               bitmap_clear (&bb_info->gen);
1837               bitmap_clear (&bb_info->kill);
1838
1839               df_live_bb_local_compute (bb->index);
1840               gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1841               gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1842             }
1843         }
1844       else
1845         {
1846           /* If we do not have basic block info, the block must be in
1847              the list of dirty blocks or else some one has added a
1848              block behind our backs. */
1849           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1850                                     bb->index));
1851         }
1852       /* Make sure no one created a block without following
1853          procedures.  */
1854       gcc_assert (df_scan_get_bb_info (bb->index));
1855     }
1856
1857   /* Make sure there are no dirty bits in blocks that have been deleted.  */
1858   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1859                                          &all_blocks));
1860   bitmap_clear (&saved_gen);
1861   bitmap_clear (&saved_kill);
1862   bitmap_clear (&all_blocks);
1863 }
1864 \f
1865 /*----------------------------------------------------------------------------
1866    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1867
1868    Link either the defs to the uses and / or the uses to the defs.
1869
1870    These problems are set up like the other dataflow problems so that
1871    they nicely fit into the framework.  They are much simpler and only
1872    involve a single traversal of instructions and an examination of
1873    the reaching defs information (the dependent problem).
1874 ----------------------------------------------------------------------------*/
1875
1876 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1877
1878 /* Create a du or ud chain from SRC to DST and link it into SRC.   */
1879
1880 struct df_link *
1881 df_chain_create (df_ref src, df_ref dst)
1882 {
1883   struct df_link *head = DF_REF_CHAIN (src);
1884   struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1885
1886   DF_REF_CHAIN (src) = link;
1887   link->next = head;
1888   link->ref = dst;
1889   return link;
1890 }
1891
1892
1893 /* Delete any du or ud chains that start at REF and point to
1894    TARGET.  */
1895 static void
1896 df_chain_unlink_1 (df_ref ref, df_ref target)
1897 {
1898   struct df_link *chain = DF_REF_CHAIN (ref);
1899   struct df_link *prev = NULL;
1900
1901   while (chain)
1902     {
1903       if (chain->ref == target)
1904         {
1905           if (prev)
1906             prev->next = chain->next;
1907           else
1908             DF_REF_CHAIN (ref) = chain->next;
1909           pool_free (df_chain->block_pool, chain);
1910           return;
1911         }
1912       prev = chain;
1913       chain = chain->next;
1914     }
1915 }
1916
1917
1918 /* Delete a du or ud chain that leave or point to REF.  */
1919
1920 void
1921 df_chain_unlink (df_ref ref)
1922 {
1923   struct df_link *chain = DF_REF_CHAIN (ref);
1924   while (chain)
1925     {
1926       struct df_link *next = chain->next;
1927       /* Delete the other side if it exists.  */
1928       df_chain_unlink_1 (chain->ref, ref);
1929       pool_free (df_chain->block_pool, chain);
1930       chain = next;
1931     }
1932   DF_REF_CHAIN (ref) = NULL;
1933 }
1934
1935
1936 /* Copy the du or ud chain starting at FROM_REF and attach it to
1937    TO_REF.  */
1938
1939 void
1940 df_chain_copy (df_ref to_ref,
1941                struct df_link *from_ref)
1942 {
1943   while (from_ref)
1944     {
1945       df_chain_create (to_ref, from_ref->ref);
1946       from_ref = from_ref->next;
1947     }
1948 }
1949
1950
1951 /* Remove this problem from the stack of dataflow problems.  */
1952
1953 static void
1954 df_chain_remove_problem (void)
1955 {
1956   bitmap_iterator bi;
1957   unsigned int bb_index;
1958
1959   /* Wholesale destruction of the old chains.  */
1960   if (df_chain->block_pool)
1961     free_alloc_pool (df_chain->block_pool);
1962
1963   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1964     {
1965       rtx_insn *insn;
1966       df_ref def, use;
1967       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1968
1969       if (df_chain_problem_p (DF_DU_CHAIN))
1970         FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1971           DF_REF_CHAIN (def) = NULL;
1972       if (df_chain_problem_p (DF_UD_CHAIN))
1973         FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1974           DF_REF_CHAIN (use) = NULL;
1975
1976       FOR_BB_INSNS (bb, insn)
1977         if (INSN_P (insn))
1978           {
1979             df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1980             if (df_chain_problem_p (DF_DU_CHAIN))
1981               FOR_EACH_INSN_INFO_DEF (def, insn_info)
1982                 DF_REF_CHAIN (def) = NULL;
1983             if (df_chain_problem_p (DF_UD_CHAIN))
1984               {
1985                 FOR_EACH_INSN_INFO_USE (use, insn_info)
1986                   DF_REF_CHAIN (use) = NULL;
1987                 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1988                   DF_REF_CHAIN (use) = NULL;
1989               }
1990           }
1991     }
1992
1993   bitmap_clear (df_chain->out_of_date_transfer_functions);
1994   df_chain->block_pool = NULL;
1995 }
1996
1997
1998 /* Remove the chain problem completely.  */
1999
2000 static void
2001 df_chain_fully_remove_problem (void)
2002 {
2003   df_chain_remove_problem ();
2004   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2005   free (df_chain);
2006 }
2007
2008
2009 /* Create def-use or use-def chains.  */
2010
2011 static void
2012 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2013 {
2014   df_chain_remove_problem ();
2015   df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2016                                          sizeof (struct df_link), 50);
2017   df_chain->optional_p = true;
2018 }
2019
2020
2021 /* Reset all of the chains when the set of basic blocks changes.  */
2022
2023 static void
2024 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2025 {
2026   df_chain_remove_problem ();
2027 }
2028
2029
2030 /* Create the chains for a list of USEs.  */
2031
2032 static void
2033 df_chain_create_bb_process_use (bitmap local_rd,
2034                                 df_ref use,
2035                                 int top_flag)
2036 {
2037   bitmap_iterator bi;
2038   unsigned int def_index;
2039
2040   for (; use; use = DF_REF_NEXT_LOC (use))
2041     {
2042       unsigned int uregno = DF_REF_REGNO (use);
2043       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2044           || (uregno >= FIRST_PSEUDO_REGISTER))
2045         {
2046           /* Do not want to go through this for an uninitialized var.  */
2047           int count = DF_DEFS_COUNT (uregno);
2048           if (count)
2049             {
2050               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2051                 {
2052                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
2053                   unsigned int last_index = first_index + count - 1;
2054
2055                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2056                     {
2057                       df_ref def;
2058                       if (def_index > last_index)
2059                         break;
2060
2061                       def = DF_DEFS_GET (def_index);
2062                       if (df_chain_problem_p (DF_DU_CHAIN))
2063                         df_chain_create (def, use);
2064                       if (df_chain_problem_p (DF_UD_CHAIN))
2065                         df_chain_create (use, def);
2066                     }
2067                 }
2068             }
2069         }
2070     }
2071 }
2072
2073
2074 /* Create chains from reaching defs bitmaps for basic block BB.  */
2075
2076 static void
2077 df_chain_create_bb (unsigned int bb_index)
2078 {
2079   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2080   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2081   rtx_insn *insn;
2082   bitmap_head cpy;
2083
2084   bitmap_initialize (&cpy, &bitmap_default_obstack);
2085   bitmap_copy (&cpy, &bb_info->in);
2086   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2087
2088   /* Since we are going forwards, process the artificial uses first
2089      then the artificial defs second.  */
2090
2091 #ifdef EH_USES
2092   /* Create the chains for the artificial uses from the EH_USES at the
2093      beginning of the block.  */
2094
2095   /* Artificials are only hard regs.  */
2096   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2097     df_chain_create_bb_process_use (&cpy,
2098                                     df_get_artificial_uses (bb->index),
2099                                     DF_REF_AT_TOP);
2100 #endif
2101
2102   df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2103
2104   /* Process the regular instructions next.  */
2105   FOR_BB_INSNS (bb, insn)
2106     if (INSN_P (insn))
2107       {
2108         unsigned int uid = INSN_UID (insn);
2109
2110         /* First scan the uses and link them up with the defs that remain
2111            in the cpy vector.  */
2112         df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2113         if (df->changeable_flags & DF_EQ_NOTES)
2114           df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2115
2116         /* Since we are going forwards, process the defs second.  */
2117         df_rd_simulate_one_insn (bb, insn, &cpy);
2118       }
2119
2120   /* Create the chains for the artificial uses of the hard registers
2121      at the end of the block.  */
2122   if (!(df->changeable_flags & DF_NO_HARD_REGS))
2123     df_chain_create_bb_process_use (&cpy,
2124                                     df_get_artificial_uses (bb->index),
2125                                     0);
2126
2127   bitmap_clear (&cpy);
2128 }
2129
2130 /* Create def-use chains from reaching use bitmaps for basic blocks
2131    in BLOCKS.  */
2132
2133 static void
2134 df_chain_finalize (bitmap all_blocks)
2135 {
2136   unsigned int bb_index;
2137   bitmap_iterator bi;
2138
2139   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2140     {
2141       df_chain_create_bb (bb_index);
2142     }
2143 }
2144
2145
2146 /* Free all storage associated with the problem.  */
2147
2148 static void
2149 df_chain_free (void)
2150 {
2151   free_alloc_pool (df_chain->block_pool);
2152   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2153   free (df_chain);
2154 }
2155
2156
2157 /* Debugging info.  */
2158
2159 static void
2160 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2161 {
2162   /* Artificials are only hard regs.  */
2163   if (df->changeable_flags & DF_NO_HARD_REGS)
2164     return;
2165   if (df_chain_problem_p (DF_UD_CHAIN))
2166     {
2167       df_ref use;
2168
2169       fprintf (file,
2170                ";;  UD chains for artificial uses at %s\n",
2171                top ? "top" : "bottom");
2172       FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2173         if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2174             || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2175           {
2176             fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
2177             df_chain_dump (DF_REF_CHAIN (use), file);
2178             fprintf (file, "\n");
2179           }
2180     }
2181   if (df_chain_problem_p (DF_DU_CHAIN))
2182     {
2183       df_ref def;
2184
2185       fprintf (file,
2186                ";;  DU chains for artificial defs at %s\n",
2187                top ? "top" : "bottom");
2188       FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2189         if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2190             || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2191           {
2192             fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
2193             df_chain_dump (DF_REF_CHAIN (def), file);
2194             fprintf (file, "\n");
2195           }
2196     }
2197 }
2198
2199 static void
2200 df_chain_top_dump (basic_block bb, FILE *file)
2201 {
2202   df_chain_bb_dump (bb, file, /*top=*/true);
2203 }
2204
2205 static void
2206 df_chain_bottom_dump (basic_block bb, FILE *file)
2207 {
2208   df_chain_bb_dump (bb, file, /*top=*/false);
2209 }
2210
2211 static void
2212 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2213 {
2214   if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2215     {
2216       struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2217       df_ref use;
2218
2219       fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
2220                DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2221       FOR_EACH_INSN_INFO_USE (use, insn_info)
2222         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2223             || !(df->changeable_flags & DF_NO_HARD_REGS))
2224           {
2225             fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
2226             if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2227               fprintf (file, "read/write ");
2228             df_chain_dump (DF_REF_CHAIN (use), file);
2229             fprintf (file, "\n");
2230           }
2231       FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2232         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2233             || !(df->changeable_flags & DF_NO_HARD_REGS))
2234           {
2235             fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
2236             df_chain_dump (DF_REF_CHAIN (use), file);
2237             fprintf (file, "\n");
2238           }
2239     }
2240 }
2241
2242 static void
2243 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2244 {
2245   if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2246     {
2247       struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2248       df_ref def;
2249       fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
2250                DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2251       FOR_EACH_INSN_INFO_DEF (def, insn_info)
2252         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2253             || !(df->changeable_flags & DF_NO_HARD_REGS))
2254           {
2255             fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
2256             if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2257               fprintf (file, "read/write ");
2258             df_chain_dump (DF_REF_CHAIN (def), file);
2259             fprintf (file, "\n");
2260           }
2261       fprintf (file, "\n");
2262     }
2263 }
2264
2265 static struct df_problem problem_CHAIN =
2266 {
2267   DF_CHAIN,                   /* Problem id.  */
2268   DF_NONE,                    /* Direction.  */
2269   df_chain_alloc,             /* Allocate the problem specific data.  */
2270   df_chain_reset,             /* Reset global information.  */
2271   NULL,                       /* Free basic block info.  */
2272   NULL,                       /* Local compute function.  */
2273   NULL,                       /* Init the solution specific data.  */
2274   NULL,                       /* Iterative solver.  */
2275   NULL,                       /* Confluence operator 0.  */
2276   NULL,                       /* Confluence operator n.  */
2277   NULL,                       /* Transfer function.  */
2278   df_chain_finalize,          /* Finalize function.  */
2279   df_chain_free,              /* Free all of the problem information.  */
2280   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
2281   NULL,                       /* Debugging.  */
2282   df_chain_top_dump,          /* Debugging start block.  */
2283   df_chain_bottom_dump,       /* Debugging end block.  */
2284   df_chain_insn_top_dump,     /* Debugging start insn.  */
2285   df_chain_insn_bottom_dump,  /* Debugging end insn.  */
2286   NULL,                       /* Incremental solution verify start.  */
2287   NULL,                       /* Incremental solution verify end.  */
2288   &problem_RD,                /* Dependent problem.  */
2289   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
2290   TV_DF_CHAIN,                /* Timing variable.  */
2291   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
2292 };
2293
2294
2295 /* Create a new DATAFLOW instance and add it to an existing instance
2296    of DF.  The returned structure is what is used to get at the
2297    solution.  */
2298
2299 void
2300 df_chain_add_problem (unsigned int chain_flags)
2301 {
2302   df_add_problem (&problem_CHAIN);
2303   df_chain->local_flags = chain_flags;
2304   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2305 }
2306
2307 #undef df_chain_problem_p
2308
2309 \f
2310 /*----------------------------------------------------------------------------
2311    WORD LEVEL LIVE REGISTERS
2312
2313    Find the locations in the function where any use of a pseudo can
2314    reach in the backwards direction.  In and out bitvectors are built
2315    for each basic block.  We only track pseudo registers that have a
2316    size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2317    contain two bits corresponding to each of the subwords.
2318
2319    ----------------------------------------------------------------------------*/
2320
2321 /* Private data used to verify the solution for this problem.  */
2322 struct df_word_lr_problem_data
2323 {
2324   /* An obstack for the bitmaps we need for this problem.  */
2325   bitmap_obstack word_lr_bitmaps;
2326 };
2327
2328
2329 /* Free basic block info.  */
2330
2331 static void
2332 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2333                          void *vbb_info)
2334 {
2335   struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2336   if (bb_info)
2337     {
2338       bitmap_clear (&bb_info->use);
2339       bitmap_clear (&bb_info->def);
2340       bitmap_clear (&bb_info->in);
2341       bitmap_clear (&bb_info->out);
2342     }
2343 }
2344
2345
2346 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2347    not touched unless the block is new.  */
2348
2349 static void
2350 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2351 {
2352   unsigned int bb_index;
2353   bitmap_iterator bi;
2354   basic_block bb;
2355   struct df_word_lr_problem_data *problem_data
2356     = XNEW (struct df_word_lr_problem_data);
2357
2358   df_word_lr->problem_data = problem_data;
2359
2360   df_grow_bb_info (df_word_lr);
2361
2362   /* Create the mapping from regnos to slots. This does not change
2363      unless the problem is destroyed and recreated.  In particular, if
2364      we end up deleting the only insn that used a subreg, we do not
2365      want to redo the mapping because this would invalidate everything
2366      else.  */
2367
2368   bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2369
2370   FOR_EACH_BB_FN (bb, cfun)
2371     bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2372
2373   bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2374   bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2375
2376   EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2377     {
2378       struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2379
2380       /* When bitmaps are already initialized, just clear them.  */
2381       if (bb_info->use.obstack)
2382         {
2383           bitmap_clear (&bb_info->def);
2384           bitmap_clear (&bb_info->use);
2385         }
2386       else
2387         {
2388           bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2389           bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2390           bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2391           bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2392         }
2393     }
2394
2395   df_word_lr->optional_p = true;
2396 }
2397
2398
2399 /* Reset the global solution for recalculation.  */
2400
2401 static void
2402 df_word_lr_reset (bitmap all_blocks)
2403 {
2404   unsigned int bb_index;
2405   bitmap_iterator bi;
2406
2407   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2408     {
2409       struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2410       gcc_assert (bb_info);
2411       bitmap_clear (&bb_info->in);
2412       bitmap_clear (&bb_info->out);
2413     }
2414 }
2415
2416 /* Examine REF, and if it is for a reg we're interested in, set or
2417    clear the bits corresponding to its subwords from the bitmap
2418    according to IS_SET.  LIVE is the bitmap we should update.  We do
2419    not track hard regs or pseudos of any size other than 2 *
2420    UNITS_PER_WORD.
2421    We return true if we changed the bitmap, or if we encountered a register
2422    we're not tracking.  */
2423
2424 bool
2425 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2426 {
2427   rtx orig_reg = DF_REF_REG (ref);
2428   rtx reg = orig_reg;
2429   machine_mode reg_mode;
2430   unsigned regno;
2431   /* Left at -1 for whole accesses.  */
2432   int which_subword = -1;
2433   bool changed = false;
2434
2435   if (GET_CODE (reg) == SUBREG)
2436     reg = SUBREG_REG (orig_reg);
2437   regno = REGNO (reg);
2438   reg_mode = GET_MODE (reg);
2439   if (regno < FIRST_PSEUDO_REGISTER
2440       || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
2441     return true;
2442
2443   if (GET_CODE (orig_reg) == SUBREG
2444       && df_read_modify_subreg_p (orig_reg))
2445     {
2446       gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2447       if (subreg_lowpart_p (orig_reg))
2448         which_subword = 0;
2449       else
2450         which_subword = 1;
2451     }
2452   if (is_set)
2453     {
2454       if (which_subword != 1)
2455         changed |= bitmap_set_bit (live, regno * 2);
2456       if (which_subword != 0)
2457         changed |= bitmap_set_bit (live, regno * 2 + 1);
2458     }
2459   else
2460     {
2461       if (which_subword != 1)
2462         changed |= bitmap_clear_bit (live, regno * 2);
2463       if (which_subword != 0)
2464         changed |= bitmap_clear_bit (live, regno * 2 + 1);
2465     }
2466   return changed;
2467 }
2468
2469 /* Compute local live register info for basic block BB.  */
2470
2471 static void
2472 df_word_lr_bb_local_compute (unsigned int bb_index)
2473 {
2474   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2475   struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2476   rtx_insn *insn;
2477   df_ref def, use;
2478
2479   /* Ensure that artificial refs don't contain references to pseudos.  */
2480   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2481     gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2482
2483   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2484     gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2485
2486   FOR_BB_INSNS_REVERSE (bb, insn)
2487     {
2488       if (!NONDEBUG_INSN_P (insn))
2489         continue;
2490
2491       df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2492       FOR_EACH_INSN_INFO_DEF (def, insn_info)
2493         /* If the def is to only part of the reg, it does
2494            not kill the other defs that reach here.  */
2495         if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2496           {
2497             df_word_lr_mark_ref (def, true, &bb_info->def);
2498             df_word_lr_mark_ref (def, false, &bb_info->use);
2499           }
2500       FOR_EACH_INSN_INFO_USE (use, insn_info)
2501         df_word_lr_mark_ref (use, true, &bb_info->use);
2502     }
2503 }
2504
2505
2506 /* Compute local live register info for each basic block within BLOCKS.  */
2507
2508 static void
2509 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2510 {
2511   unsigned int bb_index;
2512   bitmap_iterator bi;
2513
2514   EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2515     {
2516       if (bb_index == EXIT_BLOCK)
2517         {
2518           unsigned regno;
2519           bitmap_iterator bi;
2520           EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2521                                     regno, bi)
2522             gcc_unreachable ();
2523         }
2524       else
2525         df_word_lr_bb_local_compute (bb_index);
2526     }
2527
2528   bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2529 }
2530
2531
2532 /* Initialize the solution vectors.  */
2533
2534 static void
2535 df_word_lr_init (bitmap all_blocks)
2536 {
2537   unsigned int bb_index;
2538   bitmap_iterator bi;
2539
2540   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2541     {
2542       struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2543       bitmap_copy (&bb_info->in, &bb_info->use);
2544       bitmap_clear (&bb_info->out);
2545     }
2546 }
2547
2548
2549 /* Confluence function that ignores fake edges.  */
2550
2551 static bool
2552 df_word_lr_confluence_n (edge e)
2553 {
2554   bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2555   bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2556
2557   return bitmap_ior_into (op1, op2);
2558 }
2559
2560
2561 /* Transfer function.  */
2562
2563 static bool
2564 df_word_lr_transfer_function (int bb_index)
2565 {
2566   struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2567   bitmap in = &bb_info->in;
2568   bitmap out = &bb_info->out;
2569   bitmap use = &bb_info->use;
2570   bitmap def = &bb_info->def;
2571
2572   return bitmap_ior_and_compl (in, use, out, def);
2573 }
2574
2575
2576 /* Free all storage associated with the problem.  */
2577
2578 static void
2579 df_word_lr_free (void)
2580 {
2581   struct df_word_lr_problem_data *problem_data
2582     = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2583
2584   if (df_word_lr->block_info)
2585     {
2586       df_word_lr->block_info_size = 0;
2587       free (df_word_lr->block_info);
2588       df_word_lr->block_info = NULL;
2589     }
2590
2591   BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2592   bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2593   free (problem_data);
2594   free (df_word_lr);
2595 }
2596
2597
2598 /* Debugging info at top of bb.  */
2599
2600 static void
2601 df_word_lr_top_dump (basic_block bb, FILE *file)
2602 {
2603   struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2604   if (!bb_info)
2605     return;
2606
2607   fprintf (file, ";; blr  in  \t");
2608   df_print_word_regset (file, &bb_info->in);
2609   fprintf (file, ";; blr  use \t");
2610   df_print_word_regset (file, &bb_info->use);
2611   fprintf (file, ";; blr  def \t");
2612   df_print_word_regset (file, &bb_info->def);
2613 }
2614
2615
2616 /* Debugging info at bottom of bb.  */
2617
2618 static void
2619 df_word_lr_bottom_dump (basic_block bb, FILE *file)
2620 {
2621   struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2622   if (!bb_info)
2623     return;
2624
2625   fprintf (file, ";; blr  out \t");
2626   df_print_word_regset (file, &bb_info->out);
2627 }
2628
2629
2630 /* All of the information associated with every instance of the problem.  */
2631
2632 static struct df_problem problem_WORD_LR =
2633 {
2634   DF_WORD_LR,                      /* Problem id.  */
2635   DF_BACKWARD,                     /* Direction.  */
2636   df_word_lr_alloc,                /* Allocate the problem specific data.  */
2637   df_word_lr_reset,                /* Reset global information.  */
2638   df_word_lr_free_bb_info,         /* Free basic block info.  */
2639   df_word_lr_local_compute,        /* Local compute function.  */
2640   df_word_lr_init,                 /* Init the solution specific data.  */
2641   df_worklist_dataflow,            /* Worklist solver.  */
2642   NULL,                            /* Confluence operator 0.  */
2643   df_word_lr_confluence_n,         /* Confluence operator n.  */
2644   df_word_lr_transfer_function,    /* Transfer function.  */
2645   NULL,                            /* Finalize function.  */
2646   df_word_lr_free,                 /* Free all of the problem information.  */
2647   df_word_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
2648   NULL,                            /* Debugging.  */
2649   df_word_lr_top_dump,             /* Debugging start block.  */
2650   df_word_lr_bottom_dump,          /* Debugging end block.  */
2651   NULL,                            /* Debugging start insn.  */
2652   NULL,                            /* Debugging end insn.  */
2653   NULL,                            /* Incremental solution verify start.  */
2654   NULL,                            /* Incremental solution verify end.  */
2655   NULL,                            /* Dependent problem.  */
2656   sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array.  */
2657   TV_DF_WORD_LR,                   /* Timing variable.  */
2658   false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
2659 };
2660
2661
2662 /* Create a new DATAFLOW instance and add it to an existing instance
2663    of DF.  The returned structure is what is used to get at the
2664    solution.  */
2665
2666 void
2667 df_word_lr_add_problem (void)
2668 {
2669   df_add_problem (&problem_WORD_LR);
2670   /* These will be initialized when df_scan_blocks processes each
2671      block.  */
2672   df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2673 }
2674
2675
2676 /* Simulate the effects of the defs of INSN on LIVE.  Return true if we changed
2677    any bits, which is used by the caller to determine whether a set is
2678    necessary.  We also return true if there are other reasons not to delete
2679    an insn.  */
2680
2681 bool
2682 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
2683 {
2684   bool changed = false;
2685   df_ref def;
2686
2687   FOR_EACH_INSN_DEF (def, insn)
2688     if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
2689       changed = true;
2690     else
2691       changed |= df_word_lr_mark_ref (def, false, live);
2692   return changed;
2693 }
2694
2695
2696 /* Simulate the effects of the uses of INSN on LIVE.  */
2697
2698 void
2699 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
2700 {
2701   df_ref use;
2702
2703   FOR_EACH_INSN_USE (use, insn)
2704     df_word_lr_mark_ref (use, true, live);
2705 }
2706 \f
2707 /*----------------------------------------------------------------------------
2708    This problem computes REG_DEAD and REG_UNUSED notes.
2709    ----------------------------------------------------------------------------*/
2710
2711 static void
2712 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2713 {
2714   df_note->optional_p = true;
2715 }
2716
2717 /* This is only used if REG_DEAD_DEBUGGING is in effect.  */
2718 static void
2719 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
2720 {
2721   if (dump_file)
2722     {
2723       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2724       print_rtl (dump_file, note);
2725       fprintf (dump_file, "\n");
2726     }
2727 }
2728
2729
2730 /* After reg-stack, the x86 floating point stack regs are difficult to
2731    analyze because of all of the pushes, pops and rotations.  Thus, we
2732    just leave the notes alone. */
2733
2734 #ifdef STACK_REGS
2735 static inline bool
2736 df_ignore_stack_reg (int regno)
2737 {
2738   return regstack_completed
2739     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2740 }
2741 #else
2742 static inline bool
2743 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2744 {
2745   return false;
2746 }
2747 #endif
2748
2749
2750 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN.  */
2751
2752 static void
2753 df_remove_dead_and_unused_notes (rtx_insn *insn)
2754 {
2755   rtx *pprev = &REG_NOTES (insn);
2756   rtx link = *pprev;
2757
2758   while (link)
2759     {
2760       switch (REG_NOTE_KIND (link))
2761         {
2762         case REG_DEAD:
2763           /* After reg-stack, we need to ignore any unused notes
2764              for the stack registers.  */
2765           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2766             {
2767               pprev = &XEXP (link, 1);
2768               link = *pprev;
2769             }
2770           else
2771             {
2772               rtx next = XEXP (link, 1);
2773               if (REG_DEAD_DEBUGGING)
2774                 df_print_note ("deleting: ", insn, link);
2775               free_EXPR_LIST_node (link);
2776               *pprev = link = next;
2777             }
2778           break;
2779
2780         case REG_UNUSED:
2781           /* After reg-stack, we need to ignore any unused notes
2782              for the stack registers.  */
2783           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2784             {
2785               pprev = &XEXP (link, 1);
2786               link = *pprev;
2787             }
2788           else
2789             {
2790               rtx next = XEXP (link, 1);
2791               if (REG_DEAD_DEBUGGING)
2792                 df_print_note ("deleting: ", insn, link);
2793               free_EXPR_LIST_node (link);
2794               *pprev = link = next;
2795             }
2796           break;
2797
2798         default:
2799           pprev = &XEXP (link, 1);
2800           link = *pprev;
2801           break;
2802         }
2803     }
2804 }
2805
2806 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2807    as the bitmap of currently live registers.  */
2808
2809 static void
2810 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
2811 {
2812   rtx *pprev = &REG_NOTES (insn);
2813   rtx link = *pprev;
2814
2815   while (link)
2816     {
2817       switch (REG_NOTE_KIND (link))
2818         {
2819         case REG_EQUAL:
2820         case REG_EQUIV:
2821           {
2822             /* Remove the notes that refer to dead registers.  As we have at most
2823                one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2824                so we need to purge the complete EQ_USES vector when removing
2825                the note using df_notes_rescan.  */
2826             df_ref use;
2827             bool deleted = false;
2828
2829             FOR_EACH_INSN_EQ_USE (use, insn)
2830               if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
2831                   && DF_REF_LOC (use)
2832                   && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
2833                   && !bitmap_bit_p (live, DF_REF_REGNO (use))
2834                   && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
2835                 {
2836                   deleted = true;
2837                   break;
2838                 }
2839             if (deleted)
2840               {
2841                 rtx next;
2842                 if (REG_DEAD_DEBUGGING)
2843                   df_print_note ("deleting: ", insn, link);
2844                 next = XEXP (link, 1);
2845                 free_EXPR_LIST_node (link);
2846                 *pprev = link = next;
2847                 df_notes_rescan (insn);
2848               }
2849             else
2850               {
2851                 pprev = &XEXP (link, 1);
2852                 link = *pprev;
2853               }
2854             break;
2855           }
2856
2857         default:
2858           pprev = &XEXP (link, 1);
2859           link = *pprev;
2860           break;
2861         }
2862     }
2863 }
2864
2865 /* Set a NOTE_TYPE note for REG in INSN.  */
2866
2867 static inline void
2868 df_set_note (enum reg_note note_type, rtx insn, rtx reg)
2869 {
2870   gcc_checking_assert (!DEBUG_INSN_P (insn));
2871   add_reg_note (insn, note_type, reg);
2872 }
2873
2874 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2875    arguments.  Return true if the register value described by MWS's
2876    mw_reg is known to be completely unused, and if mw_reg can therefore
2877    be used in a REG_UNUSED note.  */
2878
2879 static bool
2880 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2881                           bitmap live, bitmap artificial_uses)
2882 {
2883   unsigned int r;
2884
2885   /* If MWS describes a partial reference, create REG_UNUSED notes for
2886      individual hard registers.  */
2887   if (mws->flags & DF_REF_PARTIAL)
2888     return false;
2889
2890   /* Likewise if some part of the register is used.  */
2891   for (r = mws->start_regno; r <= mws->end_regno; r++)
2892     if (bitmap_bit_p (live, r)
2893         || bitmap_bit_p (artificial_uses, r))
2894       return false;
2895
2896   gcc_assert (REG_P (mws->mw_reg));
2897   return true;
2898 }
2899
2900
2901 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2902    based on the bits in LIVE.  Do not generate notes for registers in
2903    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
2904    not generated if the reg is both read and written by the
2905    instruction.
2906 */
2907
2908 static void
2909 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2910                             bitmap live, bitmap do_not_gen,
2911                             bitmap artificial_uses,
2912                             struct dead_debug_local *debug)
2913 {
2914   unsigned int r;
2915
2916   if (REG_DEAD_DEBUGGING && dump_file)
2917     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2918              mws->start_regno, mws->end_regno);
2919
2920   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2921     {
2922       unsigned int regno = mws->start_regno;
2923       df_set_note (REG_UNUSED, insn, mws->mw_reg);
2924       dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
2925
2926       if (REG_DEAD_DEBUGGING)
2927         df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2928
2929       bitmap_set_bit (do_not_gen, regno);
2930       /* Only do this if the value is totally dead.  */
2931     }
2932   else
2933     for (r = mws->start_regno; r <= mws->end_regno; r++)
2934       {
2935         if (!bitmap_bit_p (live, r)
2936             && !bitmap_bit_p (artificial_uses, r))
2937           {
2938             df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
2939             dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
2940             if (REG_DEAD_DEBUGGING)
2941               df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2942           }
2943         bitmap_set_bit (do_not_gen, r);
2944       }
2945 }
2946
2947
2948 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2949    arguments.  Return true if the register value described by MWS's
2950    mw_reg is known to be completely dead, and if mw_reg can therefore
2951    be used in a REG_DEAD note.  */
2952
2953 static bool
2954 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2955                         bitmap live, bitmap artificial_uses,
2956                         bitmap do_not_gen)
2957 {
2958   unsigned int r;
2959
2960   /* If MWS describes a partial reference, create REG_DEAD notes for
2961      individual hard registers.  */
2962   if (mws->flags & DF_REF_PARTIAL)
2963     return false;
2964
2965   /* Likewise if some part of the register is not dead.  */
2966   for (r = mws->start_regno; r <= mws->end_regno; r++)
2967     if (bitmap_bit_p (live, r)
2968         || bitmap_bit_p (artificial_uses, r)
2969         || bitmap_bit_p (do_not_gen, r))
2970       return false;
2971
2972   gcc_assert (REG_P (mws->mw_reg));
2973   return true;
2974 }
2975
2976 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2977    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
2978    from being set if the instruction both reads and writes the
2979    register.  */
2980
2981 static void
2982 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2983                           bitmap live, bitmap do_not_gen,
2984                           bitmap artificial_uses, bool *added_notes_p)
2985 {
2986   unsigned int r;
2987   bool is_debug = *added_notes_p;
2988
2989   *added_notes_p = false;
2990
2991   if (REG_DEAD_DEBUGGING && dump_file)
2992     {
2993       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
2994                mws->start_regno, mws->end_regno);
2995       df_print_regset (dump_file, do_not_gen);
2996       fprintf (dump_file, "  live =");
2997       df_print_regset (dump_file, live);
2998       fprintf (dump_file, "  artificial uses =");
2999       df_print_regset (dump_file, artificial_uses);
3000     }
3001
3002   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3003     {
3004       if (is_debug)
3005         {
3006           *added_notes_p = true;
3007           return;
3008         }
3009       /* Add a dead note for the entire multi word register.  */
3010       df_set_note (REG_DEAD, insn, mws->mw_reg);
3011       if (REG_DEAD_DEBUGGING)
3012         df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3013     }
3014   else
3015     {
3016       for (r = mws->start_regno; r <= mws->end_regno; r++)
3017         if (!bitmap_bit_p (live, r)
3018             && !bitmap_bit_p (artificial_uses, r)
3019             && !bitmap_bit_p (do_not_gen, r))
3020           {
3021             if (is_debug)
3022               {
3023                 *added_notes_p = true;
3024                 return;
3025               }
3026             df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3027             if (REG_DEAD_DEBUGGING)
3028               df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3029           }
3030     }
3031   return;
3032 }
3033
3034
3035 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3036    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
3037
3038 static void
3039 df_create_unused_note (rtx_insn *insn, df_ref def,
3040                        bitmap live, bitmap artificial_uses,
3041                        struct dead_debug_local *debug)
3042 {
3043   unsigned int dregno = DF_REF_REGNO (def);
3044
3045   if (REG_DEAD_DEBUGGING && dump_file)
3046     {
3047       fprintf (dump_file, "  regular looking at def ");
3048       df_ref_debug (def, dump_file);
3049     }
3050
3051   if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3052         || bitmap_bit_p (live, dregno)
3053         || bitmap_bit_p (artificial_uses, dregno)
3054         || df_ignore_stack_reg (dregno)))
3055     {
3056       rtx reg = (DF_REF_LOC (def))
3057                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3058       df_set_note (REG_UNUSED, insn, reg);
3059       dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3060       if (REG_DEAD_DEBUGGING)
3061         df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3062     }
3063
3064   return;
3065 }
3066
3067
3068 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3069    info: lifetime, bb, and number of defs and uses for basic block
3070    BB.  The three bitvectors are scratch regs used here.  */
3071
3072 static void
3073 df_note_bb_compute (unsigned int bb_index,
3074                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3075 {
3076   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3077   rtx_insn *insn;
3078   df_ref def, use;
3079   struct dead_debug_local debug;
3080
3081   dead_debug_local_init (&debug, NULL, NULL);
3082
3083   bitmap_copy (live, df_get_live_out (bb));
3084   bitmap_clear (artificial_uses);
3085
3086   if (REG_DEAD_DEBUGGING && dump_file)
3087     {
3088       fprintf (dump_file, "live at bottom ");
3089       df_print_regset (dump_file, live);
3090     }
3091
3092   /* Process the artificial defs and uses at the bottom of the block
3093      to begin processing.  */
3094   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3095     {
3096       if (REG_DEAD_DEBUGGING && dump_file)
3097         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3098
3099       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3100         bitmap_clear_bit (live, DF_REF_REGNO (def));
3101     }
3102
3103   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3104     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3105       {
3106         unsigned int regno = DF_REF_REGNO (use);
3107         bitmap_set_bit (live, regno);
3108
3109         /* Notes are not generated for any of the artificial registers
3110            at the bottom of the block.  */
3111         bitmap_set_bit (artificial_uses, regno);
3112       }
3113
3114   if (REG_DEAD_DEBUGGING && dump_file)
3115     {
3116       fprintf (dump_file, "live before artificials out ");
3117       df_print_regset (dump_file, live);
3118     }
3119
3120   FOR_BB_INSNS_REVERSE (bb, insn)
3121     {
3122       df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3123       df_mw_hardreg *mw;
3124       int debug_insn;
3125
3126       if (!INSN_P (insn))
3127         continue;
3128
3129       debug_insn = DEBUG_INSN_P (insn);
3130
3131       bitmap_clear (do_not_gen);
3132       df_remove_dead_and_unused_notes (insn);
3133
3134       /* Process the defs.  */
3135       if (CALL_P (insn))
3136         {
3137           if (REG_DEAD_DEBUGGING && dump_file)
3138             {
3139               fprintf (dump_file, "processing call %d\n  live =",
3140                        INSN_UID (insn));
3141               df_print_regset (dump_file, live);
3142             }
3143
3144           /* We only care about real sets for calls.  Clobbers cannot
3145              be depended on to really die.  */
3146           FOR_EACH_INSN_INFO_MW (mw, insn_info)
3147             if ((DF_MWS_REG_DEF_P (mw))
3148                 && !df_ignore_stack_reg (mw->start_regno))
3149               df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3150                                           artificial_uses, &debug);
3151
3152           /* All of the defs except the return value are some sort of
3153              clobber.  This code is for the return.  */
3154           FOR_EACH_INSN_INFO_DEF (def, insn_info)
3155             {
3156               unsigned int dregno = DF_REF_REGNO (def);
3157               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3158                 {
3159                   df_create_unused_note (insn,
3160                                          def, live, artificial_uses, &debug);
3161                   bitmap_set_bit (do_not_gen, dregno);
3162                 }
3163
3164               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3165                 bitmap_clear_bit (live, dregno);
3166             }
3167         }
3168       else
3169         {
3170           /* Regular insn.  */
3171           FOR_EACH_INSN_INFO_MW (mw, insn_info)
3172             if (DF_MWS_REG_DEF_P (mw))
3173               df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3174                                           artificial_uses, &debug);
3175
3176           FOR_EACH_INSN_INFO_DEF (def, insn_info)
3177             {
3178               unsigned int dregno = DF_REF_REGNO (def);
3179               df_create_unused_note (insn,
3180                                      def, live, artificial_uses, &debug);
3181
3182               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3183                 bitmap_set_bit (do_not_gen, dregno);
3184
3185               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3186                 bitmap_clear_bit (live, dregno);
3187             }
3188         }
3189
3190       /* Process the uses.  */
3191       FOR_EACH_INSN_INFO_MW (mw, insn_info)
3192         if (DF_MWS_REG_USE_P (mw)
3193             && !df_ignore_stack_reg (mw->start_regno))
3194           {
3195             bool really_add_notes = debug_insn != 0;
3196
3197             df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3198                                       artificial_uses,
3199                                       &really_add_notes);
3200
3201             if (really_add_notes)
3202               debug_insn = -1;
3203           }
3204
3205       FOR_EACH_INSN_INFO_USE (use, insn_info)
3206         {
3207           unsigned int uregno = DF_REF_REGNO (use);
3208
3209           if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3210             {
3211               fprintf (dump_file, "  regular looking at use ");
3212               df_ref_debug (use, dump_file);
3213             }
3214
3215           if (!bitmap_bit_p (live, uregno))
3216             {
3217               if (debug_insn)
3218                 {
3219                   if (debug_insn > 0)
3220                     {
3221                       /* We won't add REG_UNUSED or REG_DEAD notes for
3222                          these, so we don't have to mess with them in
3223                          debug insns either.  */
3224                       if (!bitmap_bit_p (artificial_uses, uregno)
3225                           && !df_ignore_stack_reg (uregno))
3226                         dead_debug_add (&debug, use, uregno);
3227                       continue;
3228                     }
3229                   break;
3230                 }
3231               else
3232                 dead_debug_insert_temp (&debug, uregno, insn,
3233                                         DEBUG_TEMP_BEFORE_WITH_REG);
3234
3235               if ( (!(DF_REF_FLAGS (use)
3236                       & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3237                    && (!bitmap_bit_p (do_not_gen, uregno))
3238                    && (!bitmap_bit_p (artificial_uses, uregno))
3239                    && (!df_ignore_stack_reg (uregno)))
3240                 {
3241                   rtx reg = (DF_REF_LOC (use))
3242                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3243                   df_set_note (REG_DEAD, insn, reg);
3244
3245                   if (REG_DEAD_DEBUGGING)
3246                     df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3247                 }
3248               /* This register is now live.  */
3249               bitmap_set_bit (live, uregno);
3250             }
3251         }
3252
3253       df_remove_dead_eq_notes (insn, live);
3254
3255       if (debug_insn == -1)
3256         {
3257           /* ??? We could probably do better here, replacing dead
3258              registers with their definitions.  */
3259           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3260           df_insn_rescan_debug_internal (insn);
3261         }
3262     }
3263
3264   dead_debug_local_finish (&debug, NULL);
3265 }
3266
3267
3268 /* Compute register info: lifetime, bb, and number of defs and uses.  */
3269 static void
3270 df_note_compute (bitmap all_blocks)
3271 {
3272   unsigned int bb_index;
3273   bitmap_iterator bi;
3274   bitmap_head live, do_not_gen, artificial_uses;
3275
3276   bitmap_initialize (&live, &df_bitmap_obstack);
3277   bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3278   bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3279
3280   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3281   {
3282     /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3283        pseudos in debug insns because we don't always (re)visit blocks
3284        with death points after visiting dead uses.  Even changing this
3285        loop to postorder would still leave room for visiting a death
3286        point before visiting a subsequent debug use.  */
3287     df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3288   }
3289
3290   bitmap_clear (&live);
3291   bitmap_clear (&do_not_gen);
3292   bitmap_clear (&artificial_uses);
3293 }
3294
3295
3296 /* Free all storage associated with the problem.  */
3297
3298 static void
3299 df_note_free (void)
3300 {
3301   free (df_note);
3302 }
3303
3304
3305 /* All of the information associated every instance of the problem.  */
3306
3307 static struct df_problem problem_NOTE =
3308 {
3309   DF_NOTE,                    /* Problem id.  */
3310   DF_NONE,                    /* Direction.  */
3311   df_note_alloc,              /* Allocate the problem specific data.  */
3312   NULL,                       /* Reset global information.  */
3313   NULL,                       /* Free basic block info.  */
3314   df_note_compute,            /* Local compute function.  */
3315   NULL,                       /* Init the solution specific data.  */
3316   NULL,                       /* Iterative solver.  */
3317   NULL,                       /* Confluence operator 0.  */
3318   NULL,                       /* Confluence operator n.  */
3319   NULL,                       /* Transfer function.  */
3320   NULL,                       /* Finalize function.  */
3321   df_note_free,               /* Free all of the problem information.  */
3322   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
3323   NULL,                       /* Debugging.  */
3324   NULL,                       /* Debugging start block.  */
3325   NULL,                       /* Debugging end block.  */
3326   NULL,                       /* Debugging start insn.  */
3327   NULL,                       /* Debugging end insn.  */
3328   NULL,                       /* Incremental solution verify start.  */
3329   NULL,                       /* Incremental solution verify end.  */
3330   &problem_LR,                /* Dependent problem.  */
3331   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
3332   TV_DF_NOTE,                 /* Timing variable.  */
3333   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
3334 };
3335
3336
3337 /* Create a new DATAFLOW instance and add it to an existing instance
3338    of DF.  The returned structure is what is used to get at the
3339    solution.  */
3340
3341 void
3342 df_note_add_problem (void)
3343 {
3344   df_add_problem (&problem_NOTE);
3345 }
3346
3347
3348
3349 \f
3350 /*----------------------------------------------------------------------------
3351    Functions for simulating the effects of single insns.
3352
3353    You can either simulate in the forwards direction, starting from
3354    the top of a block or the backwards direction from the end of the
3355    block.  If you go backwards, defs are examined first to clear bits,
3356    then uses are examined to set bits.  If you go forwards, defs are
3357    examined first to set bits, then REG_DEAD and REG_UNUSED notes
3358    are examined to clear bits.  In either case, the result of examining
3359    a def can be undone (respectively by a use or a REG_UNUSED note).
3360
3361    If you start at the top of the block, use one of DF_LIVE_IN or
3362    DF_LR_IN.  If you start at the bottom of the block use one of
3363    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
3364    THEY WILL BE DESTROYED.
3365 ----------------------------------------------------------------------------*/
3366
3367
3368 /* Find the set of DEFs for INSN.  */
3369
3370 void
3371 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3372 {
3373   df_ref def;
3374
3375   FOR_EACH_INSN_DEF (def, insn)
3376     bitmap_set_bit (defs, DF_REF_REGNO (def));
3377 }
3378
3379 /* Find the set of uses for INSN.  This includes partial defs.  */
3380
3381 static void
3382 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3383 {
3384   df_ref def, use;
3385   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3386
3387   FOR_EACH_INSN_INFO_DEF (def, insn_info)
3388     if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3389       bitmap_set_bit (uses, DF_REF_REGNO (def));
3390   FOR_EACH_INSN_INFO_USE (use, insn_info)
3391     bitmap_set_bit (uses, DF_REF_REGNO (use));
3392 }
3393
3394 /* Find the set of real DEFs, which are not clobbers, for INSN.  */
3395
3396 void
3397 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3398 {
3399   df_ref def;
3400
3401   FOR_EACH_INSN_DEF (def, insn)
3402     if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3403       bitmap_set_bit (defs, DF_REF_REGNO (def));
3404 }
3405
3406
3407 /* Simulate the effects of the defs of INSN on LIVE.  */
3408
3409 void
3410 df_simulate_defs (rtx_insn *insn, bitmap live)
3411 {
3412   df_ref def;
3413
3414   FOR_EACH_INSN_DEF (def, insn)
3415     {
3416       unsigned int dregno = DF_REF_REGNO (def);
3417
3418       /* If the def is to only part of the reg, it does
3419          not kill the other defs that reach here.  */
3420       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3421         bitmap_clear_bit (live, dregno);
3422     }
3423 }
3424
3425
3426 /* Simulate the effects of the uses of INSN on LIVE.  */
3427
3428 void
3429 df_simulate_uses (rtx_insn *insn, bitmap live)
3430 {
3431   df_ref use;
3432
3433   if (DEBUG_INSN_P (insn))
3434     return;
3435
3436   FOR_EACH_INSN_USE (use, insn)
3437     /* Add use to set of uses in this BB.  */
3438     bitmap_set_bit (live, DF_REF_REGNO (use));
3439 }
3440
3441
3442 /* Add back the always live regs in BB to LIVE.  */
3443
3444 static inline void
3445 df_simulate_fixup_sets (basic_block bb, bitmap live)
3446 {
3447   /* These regs are considered always live so if they end up dying
3448      because of some def, we need to bring the back again.  */
3449   if (bb_has_eh_pred (bb))
3450     bitmap_ior_into (live, &df->eh_block_artificial_uses);
3451   else
3452     bitmap_ior_into (live, &df->regular_block_artificial_uses);
3453 }
3454
3455
3456 /*----------------------------------------------------------------------------
3457    The following three functions are used only for BACKWARDS scanning:
3458    i.e. they process the defs before the uses.
3459
3460    df_simulate_initialize_backwards should be called first with a
3461    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
3462    df_simulate_one_insn_backwards should be called for each insn in
3463    the block, starting with the last one.  Finally,
3464    df_simulate_finalize_backwards can be called to get a new value
3465    of the sets at the top of the block (this is rarely used).
3466    ----------------------------------------------------------------------------*/
3467
3468 /* Apply the artificial uses and defs at the end of BB in a backwards
3469    direction.  */
3470
3471 void
3472 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3473 {
3474   df_ref def, use;
3475   int bb_index = bb->index;
3476
3477   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3478     if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3479       bitmap_clear_bit (live, DF_REF_REGNO (def));
3480
3481   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3482     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3483       bitmap_set_bit (live, DF_REF_REGNO (use));
3484 }
3485
3486
3487 /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
3488
3489 void
3490 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3491 {
3492   if (!NONDEBUG_INSN_P (insn))
3493     return;
3494
3495   df_simulate_defs (insn, live);
3496   df_simulate_uses (insn, live);
3497   df_simulate_fixup_sets (bb, live);
3498 }
3499
3500
3501 /* Apply the artificial uses and defs at the top of BB in a backwards
3502    direction.  */
3503
3504 void
3505 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3506 {
3507   df_ref def;
3508 #ifdef EH_USES
3509   df_ref use;
3510 #endif
3511   int bb_index = bb->index;
3512
3513   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3514     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3515       bitmap_clear_bit (live, DF_REF_REGNO (def));
3516
3517 #ifdef EH_USES
3518   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3519     if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3520       bitmap_set_bit (live, DF_REF_REGNO (use));
3521 #endif
3522 }
3523 /*----------------------------------------------------------------------------
3524    The following three functions are used only for FORWARDS scanning:
3525    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3526    Thus it is important to add the DF_NOTES problem to the stack of
3527    problems computed before using these functions.
3528
3529    df_simulate_initialize_forwards should be called first with a
3530    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
3531    df_simulate_one_insn_forwards should be called for each insn in
3532    the block, starting with the first one.
3533    ----------------------------------------------------------------------------*/
3534
3535 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3536    DF_LR_IN for basic block BB, for forward scanning by marking artificial
3537    defs live.  */
3538
3539 void
3540 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3541 {
3542   df_ref def;
3543   int bb_index = bb->index;
3544
3545   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3546     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3547       bitmap_set_bit (live, DF_REF_REGNO (def));
3548 }
3549
3550 /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
3551
3552 void
3553 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3554 {
3555   rtx link;
3556   if (! INSN_P (insn))
3557     return;
3558
3559   /* Make sure that DF_NOTE really is an active df problem.  */
3560   gcc_assert (df_note);
3561
3562   /* Note that this is the opposite as how the problem is defined, because
3563      in the LR problem defs _kill_ liveness.  However, they do so backwards,
3564      while here the scan is performed forwards!  So, first assume that the
3565      def is live, and if this is not true REG_UNUSED notes will rectify the
3566      situation.  */
3567   df_simulate_find_noclobber_defs (insn, live);
3568
3569   /* Clear all of the registers that go dead.  */
3570   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3571     {
3572       switch (REG_NOTE_KIND (link))
3573         {
3574         case REG_DEAD:
3575         case REG_UNUSED:
3576           {
3577             rtx reg = XEXP (link, 0);
3578             int regno = REGNO (reg);
3579             if (HARD_REGISTER_NUM_P (regno))
3580               bitmap_clear_range (live, regno,
3581                                   hard_regno_nregs[regno][GET_MODE (reg)]);
3582             else
3583               bitmap_clear_bit (live, regno);
3584           }
3585           break;
3586         default:
3587           break;
3588         }
3589     }
3590   df_simulate_fixup_sets (bb, live);
3591 }
3592 \f
3593 /* Used by the next two functions to encode information about the
3594    memory references we found.  */
3595 #define MEMREF_NORMAL 1
3596 #define MEMREF_VOLATILE 2
3597
3598 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X.  */
3599
3600 static int
3601 find_memory (rtx insn)
3602 {
3603   int flags = 0;
3604   subrtx_iterator::array_type array;
3605   FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3606     {
3607       const_rtx x = *iter;
3608       if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3609         flags |= MEMREF_VOLATILE;
3610       else if (MEM_P (x))
3611         {
3612           if (MEM_VOLATILE_P (x))
3613             flags |= MEMREF_VOLATILE;
3614           else if (!MEM_READONLY_P (x))
3615             flags |= MEMREF_NORMAL;
3616         }
3617     }
3618   return flags;
3619 }
3620
3621 /* A subroutine of can_move_insns_across_p called through note_stores.
3622    DATA points to an integer in which we set either the bit for
3623    MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3624    of either kind.  */
3625
3626 static void
3627 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
3628                     void *data ATTRIBUTE_UNUSED)
3629 {
3630   int *pflags = (int *)data;
3631   if (GET_CODE (x) == SUBREG)
3632     x = XEXP (x, 0);
3633   /* Treat stores to SP as stores to memory, this will prevent problems
3634      when there are references to the stack frame.  */
3635   if (x == stack_pointer_rtx)
3636     *pflags |= MEMREF_VOLATILE;
3637   if (!MEM_P (x))
3638     return;
3639   *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
3640 }
3641
3642 /* Scan BB backwards, using df_simulate functions to keep track of
3643    lifetimes, up to insn POINT.  The result is stored in LIVE.  */
3644
3645 void
3646 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
3647 {
3648   rtx_insn *insn;
3649   bitmap_copy (live, df_get_live_out (bb));
3650   df_simulate_initialize_backwards (bb, live);
3651
3652   /* Scan and update life information until we reach the point we're
3653      interested in.  */
3654   for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
3655     df_simulate_one_insn_backwards (bb, insn, live);
3656 }
3657
3658 /* Return true if it is safe to move a group of insns, described by
3659    the range FROM to TO, backwards across another group of insns,
3660    described by ACROSS_FROM to ACROSS_TO.  It is assumed that there
3661    are no insns between ACROSS_TO and FROM, but they may be in
3662    different basic blocks; MERGE_BB is the block from which the
3663    insns will be moved.  The caller must pass in a regset MERGE_LIVE
3664    which specifies the registers live after TO.
3665
3666    This function may be called in one of two cases: either we try to
3667    move identical instructions from all successor blocks into their
3668    predecessor, or we try to move from only one successor block.  If
3669    OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3670    the second case.  It should contain a set of registers live at the
3671    end of ACROSS_TO which must not be clobbered by moving the insns.
3672    In that case, we're also more careful about moving memory references
3673    and trapping insns.
3674
3675    We return false if it is not safe to move the entire group, but it
3676    may still be possible to move a subgroup.  PMOVE_UPTO, if nonnull,
3677    is set to point at the last moveable insn in such a case.  */
3678
3679 bool
3680 can_move_insns_across (rtx_insn *from, rtx_insn *to,
3681                        rtx_insn *across_from, rtx_insn *across_to,
3682                        basic_block merge_bb, regset merge_live,
3683                        regset other_branch_live, rtx_insn **pmove_upto)
3684 {
3685   rtx_insn *insn, *next, *max_to;
3686   bitmap merge_set, merge_use, local_merge_live;
3687   bitmap test_set, test_use;
3688   unsigned i, fail = 0;
3689   bitmap_iterator bi;
3690   int memrefs_in_across = 0;
3691   int mem_sets_in_across = 0;
3692   bool trapping_insns_in_across = false;
3693
3694   if (pmove_upto != NULL)
3695     *pmove_upto = NULL;
3696
3697   /* Find real bounds, ignoring debug insns.  */
3698   while (!NONDEBUG_INSN_P (from) && from != to)
3699     from = NEXT_INSN (from);
3700   while (!NONDEBUG_INSN_P (to) && from != to)
3701     to = PREV_INSN (to);
3702
3703   for (insn = across_to; ; insn = next)
3704     {
3705       if (CALL_P (insn))
3706         {
3707           if (RTL_CONST_OR_PURE_CALL_P (insn))
3708             /* Pure functions can read from memory.  Const functions can
3709                read from arguments that the ABI has forced onto the stack.
3710                Neither sort of read can be volatile.  */
3711             memrefs_in_across |= MEMREF_NORMAL;
3712           else
3713             {
3714               memrefs_in_across |= MEMREF_VOLATILE;
3715               mem_sets_in_across |= MEMREF_VOLATILE;
3716             }
3717         }
3718       if (NONDEBUG_INSN_P (insn))
3719         {
3720           if (volatile_insn_p (PATTERN (insn)))
3721             return false;
3722           memrefs_in_across |= find_memory (insn);
3723           note_stores (PATTERN (insn), find_memory_stores,
3724                        &mem_sets_in_across);
3725           /* This is used just to find sets of the stack pointer.  */
3726           memrefs_in_across |= mem_sets_in_across;
3727           trapping_insns_in_across |= may_trap_p (PATTERN (insn));
3728         }
3729       next = PREV_INSN (insn);
3730       if (insn == across_from)
3731         break;
3732     }
3733
3734   /* Collect:
3735      MERGE_SET = set of registers set in MERGE_BB
3736      MERGE_USE = set of registers used in MERGE_BB and live at its top
3737      MERGE_LIVE = set of registers live at the point inside the MERGE
3738      range that we've reached during scanning
3739      TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3740      TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3741      and live before ACROSS_FROM.  */
3742
3743   merge_set = BITMAP_ALLOC (&reg_obstack);
3744   merge_use = BITMAP_ALLOC (&reg_obstack);
3745   local_merge_live = BITMAP_ALLOC (&reg_obstack);
3746   test_set = BITMAP_ALLOC (&reg_obstack);
3747   test_use = BITMAP_ALLOC (&reg_obstack);
3748
3749   /* Compute the set of registers set and used in the ACROSS range.  */
3750   if (other_branch_live != NULL)
3751     bitmap_copy (test_use, other_branch_live);
3752   df_simulate_initialize_backwards (merge_bb, test_use);
3753   for (insn = across_to; ; insn = next)
3754     {
3755       if (NONDEBUG_INSN_P (insn))
3756         {
3757           df_simulate_find_defs (insn, test_set);
3758           df_simulate_defs (insn, test_use);
3759           df_simulate_uses (insn, test_use);
3760         }
3761       next = PREV_INSN (insn);
3762       if (insn == across_from)
3763         break;
3764     }
3765
3766   /* Compute an upper bound for the amount of insns moved, by finding
3767      the first insn in MERGE that sets a register in TEST_USE, or uses
3768      a register in TEST_SET.  We also check for calls, trapping operations,
3769      and memory references.  */
3770   max_to = NULL;
3771   for (insn = from; ; insn = next)
3772     {
3773       if (CALL_P (insn))
3774         break;
3775       if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
3776         break;
3777       if (NONDEBUG_INSN_P (insn))
3778         {
3779           if (may_trap_or_fault_p (PATTERN (insn))
3780               && (trapping_insns_in_across
3781                   || other_branch_live != NULL
3782                   || volatile_insn_p (PATTERN (insn))))
3783             break;
3784
3785           /* We cannot move memory stores past each other, or move memory
3786              reads past stores, at least not without tracking them and
3787              calling true_dependence on every pair.
3788
3789              If there is no other branch and no memory references or
3790              sets in the ACROSS range, we can move memory references
3791              freely, even volatile ones.
3792
3793              Otherwise, the rules are as follows: volatile memory
3794              references and stores can't be moved at all, and any type
3795              of memory reference can't be moved if there are volatile
3796              accesses or stores in the ACROSS range.  That leaves
3797              normal reads, which can be moved, as the trapping case is
3798              dealt with elsewhere.  */
3799           if (other_branch_live != NULL || memrefs_in_across != 0)
3800             {
3801               int mem_ref_flags = 0;
3802               int mem_set_flags = 0;
3803               note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
3804               mem_ref_flags = find_memory (insn);
3805               /* Catch sets of the stack pointer.  */
3806               mem_ref_flags |= mem_set_flags;
3807
3808               if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
3809                 break;
3810               if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
3811                 break;
3812               if (mem_set_flags != 0
3813                   || (mem_sets_in_across != 0 && mem_ref_flags != 0))
3814                 break;
3815             }
3816           df_simulate_find_uses (insn, merge_use);
3817           /* We're only interested in uses which use a value live at
3818              the top, not one previously set in this block.  */
3819           bitmap_and_compl_into (merge_use, merge_set);
3820           df_simulate_find_defs (insn, merge_set);
3821           if (bitmap_intersect_p (merge_set, test_use)
3822               || bitmap_intersect_p (merge_use, test_set))
3823             break;
3824 #ifdef HAVE_cc0
3825           if (!sets_cc0_p (insn))
3826 #endif
3827             max_to = insn;
3828         }
3829       next = NEXT_INSN (insn);
3830       if (insn == to)
3831         break;
3832     }
3833   if (max_to != to)
3834     fail = 1;
3835
3836   if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
3837     goto out;
3838
3839   /* Now, lower this upper bound by also taking into account that
3840      a range of insns moved across ACROSS must not leave a register
3841      live at the end that will be clobbered in ACROSS.  We need to
3842      find a point where TEST_SET & LIVE == 0.
3843
3844      Insns in the MERGE range that set registers which are also set
3845      in the ACROSS range may still be moved as long as we also move
3846      later insns which use the results of the set, and make the
3847      register dead again.  This is verified by the condition stated
3848      above.  We only need to test it for registers that are set in
3849      the moved region.
3850
3851      MERGE_LIVE is provided by the caller and holds live registers after
3852      TO.  */
3853   bitmap_copy (local_merge_live, merge_live);
3854   for (insn = to; insn != max_to; insn = PREV_INSN (insn))
3855     df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
3856
3857   /* We're not interested in registers that aren't set in the moved
3858      region at all.  */
3859   bitmap_and_into (local_merge_live, merge_set);
3860   for (;;)
3861     {
3862       if (NONDEBUG_INSN_P (insn))
3863         {
3864           if (!bitmap_intersect_p (test_set, local_merge_live)
3865 #ifdef HAVE_cc0
3866               && !sets_cc0_p (insn)
3867 #endif
3868               )
3869             {
3870               max_to = insn;
3871               break;
3872             }
3873
3874           df_simulate_one_insn_backwards (merge_bb, insn,
3875                                           local_merge_live);
3876         }
3877       if (insn == from)
3878         {
3879           fail = 1;
3880           goto out;
3881         }
3882       insn = PREV_INSN (insn);
3883     }
3884
3885   if (max_to != to)
3886     fail = 1;
3887
3888   if (pmove_upto)
3889     *pmove_upto = max_to;
3890
3891   /* For small register class machines, don't lengthen lifetimes of
3892      hard registers before reload.  */
3893   if (! reload_completed
3894       && targetm.small_register_classes_for_mode_p (VOIDmode))
3895     {
3896       EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3897         {
3898           if (i < FIRST_PSEUDO_REGISTER
3899               && ! fixed_regs[i]
3900               && ! global_regs[i])
3901             {
3902               fail = 1;
3903               break;
3904             }
3905         }
3906     }
3907
3908  out:
3909   BITMAP_FREE (merge_set);
3910   BITMAP_FREE (merge_use);
3911   BITMAP_FREE (local_merge_live);
3912   BITMAP_FREE (test_set);
3913   BITMAP_FREE (test_use);
3914
3915   return !fail;
3916 }
3917
3918 \f
3919 /*----------------------------------------------------------------------------
3920    MULTIPLE DEFINITIONS
3921
3922    Find the locations in the function reached by multiple definition sites
3923    for a live pseudo.  In and out bitvectors are built for each basic
3924    block.  They are restricted for efficiency to live registers.
3925
3926    The gen and kill sets for the problem are obvious.  Together they
3927    include all defined registers in a basic block; the gen set includes
3928    registers where a partial or conditional or may-clobber definition is
3929    last in the BB, while the kill set includes registers with a complete
3930    definition coming last.  However, the computation of the dataflow
3931    itself is interesting.
3932
3933    The idea behind it comes from SSA form's iterated dominance frontier
3934    criterion for inserting PHI functions.  Just like in that case, we can use
3935    the dominance frontier to find places where multiple definitions meet;
3936    a register X defined in a basic block BB1 has multiple definitions in
3937    basic blocks in BB1's dominance frontier.
3938
3939    So, the in-set of a basic block BB2 is not just the union of the
3940    out-sets of BB2's predecessors, but includes some more bits that come
3941    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3942    the previous paragraph).  I called this set the init-set of BB2.
3943
3944       (Note: I actually use the kill-set only to build the init-set.
3945       gen bits are anyway propagated from BB1 to BB2 by dataflow).
3946
3947     For example, if you have
3948
3949        BB1 : r10 = 0
3950              r11 = 0
3951              if <...> goto BB2 else goto BB3;
3952
3953        BB2 : r10 = 1
3954              r12 = 1
3955              goto BB3;
3956
3957        BB3 :
3958
3959     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3960     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
3961     not need to iterate the dominance frontier, because we do not insert
3962     anything like PHI functions there!  Instead, dataflow will take care of
3963     propagating the information to BB3's successors.
3964    ---------------------------------------------------------------------------*/
3965
3966 /* Private data used to verify the solution for this problem.  */
3967 struct df_md_problem_data
3968 {
3969   /* An obstack for the bitmaps we need for this problem.  */
3970   bitmap_obstack md_bitmaps;
3971 };
3972
3973 /* Scratch var used by transfer functions.  This is used to do md analysis
3974    only for live registers.  */
3975 static bitmap_head df_md_scratch;
3976
3977
3978 static void
3979 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3980                     void *vbb_info)
3981 {
3982   struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
3983   if (bb_info)
3984     {
3985       bitmap_clear (&bb_info->kill);
3986       bitmap_clear (&bb_info->gen);
3987       bitmap_clear (&bb_info->init);
3988       bitmap_clear (&bb_info->in);
3989       bitmap_clear (&bb_info->out);
3990     }
3991 }
3992
3993
3994 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3995    not touched unless the block is new.  */
3996
3997 static void
3998 df_md_alloc (bitmap all_blocks)
3999 {
4000   unsigned int bb_index;
4001   bitmap_iterator bi;
4002   struct df_md_problem_data *problem_data;
4003
4004   df_grow_bb_info (df_md);
4005   if (df_md->problem_data)
4006     problem_data = (struct df_md_problem_data *) df_md->problem_data;
4007   else
4008     {
4009       problem_data = XNEW (struct df_md_problem_data);
4010       df_md->problem_data = problem_data;
4011       bitmap_obstack_initialize (&problem_data->md_bitmaps);
4012     }
4013   bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4014
4015   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4016     {
4017       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4018       /* When bitmaps are already initialized, just clear them.  */
4019       if (bb_info->init.obstack)
4020         {
4021           bitmap_clear (&bb_info->init);
4022           bitmap_clear (&bb_info->gen);
4023           bitmap_clear (&bb_info->kill);
4024           bitmap_clear (&bb_info->in);
4025           bitmap_clear (&bb_info->out);
4026         }
4027       else
4028         {
4029           bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4030           bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4031           bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4032           bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4033           bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4034         }
4035     }
4036
4037   df_md->optional_p = true;
4038 }
4039
4040 /* Add the effect of the top artificial defs of BB to the multiple definitions
4041    bitmap LOCAL_MD.  */
4042
4043 void
4044 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4045 {
4046   int bb_index = bb->index;
4047   df_ref def;
4048   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4049     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4050       {
4051         unsigned int dregno = DF_REF_REGNO (def);
4052         if (DF_REF_FLAGS (def)
4053             & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4054           bitmap_set_bit (local_md, dregno);
4055         else
4056           bitmap_clear_bit (local_md, dregno);
4057       }
4058 }
4059
4060
4061 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4062    LOCAL_MD.  */
4063
4064 void
4065 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4066                          bitmap local_md)
4067 {
4068   df_ref def;
4069
4070   FOR_EACH_INSN_DEF (def, insn)
4071     {
4072       unsigned int dregno = DF_REF_REGNO (def);
4073       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4074           || (dregno >= FIRST_PSEUDO_REGISTER))
4075         {
4076           if (DF_REF_FLAGS (def)
4077               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4078            bitmap_set_bit (local_md, DF_REF_ID (def));
4079          else
4080            bitmap_clear_bit (local_md, DF_REF_ID (def));
4081         }
4082     }
4083 }
4084
4085 static void
4086 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4087                                     df_ref def,
4088                                     int top_flag)
4089 {
4090   bitmap_clear (&seen_in_insn);
4091
4092   for (; def; def = DF_REF_NEXT_LOC (def))
4093     {
4094       unsigned int dregno = DF_REF_REGNO (def);
4095       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4096             || (dregno >= FIRST_PSEUDO_REGISTER))
4097           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4098         {
4099           if (!bitmap_bit_p (&seen_in_insn, dregno))
4100             {
4101               if (DF_REF_FLAGS (def)
4102                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4103                 {
4104                   bitmap_set_bit (&bb_info->gen, dregno);
4105                   bitmap_clear_bit (&bb_info->kill, dregno);
4106                 }
4107               else
4108                 {
4109                   /* When we find a clobber and a regular def,
4110                      make sure the regular def wins.  */
4111                   bitmap_set_bit (&seen_in_insn, dregno);
4112                   bitmap_set_bit (&bb_info->kill, dregno);
4113                   bitmap_clear_bit (&bb_info->gen, dregno);
4114                 }
4115             }
4116         }
4117     }
4118 }
4119
4120
4121 /* Compute local multiple def info for basic block BB.  */
4122
4123 static void
4124 df_md_bb_local_compute (unsigned int bb_index)
4125 {
4126   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4127   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4128   rtx_insn *insn;
4129
4130   /* Artificials are only hard regs.  */
4131   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4132     df_md_bb_local_compute_process_def (bb_info,
4133                                         df_get_artificial_defs (bb_index),
4134                                         DF_REF_AT_TOP);
4135
4136   FOR_BB_INSNS (bb, insn)
4137     {
4138       unsigned int uid = INSN_UID (insn);
4139       if (!INSN_P (insn))
4140         continue;
4141
4142       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4143     }
4144
4145   if (!(df->changeable_flags & DF_NO_HARD_REGS))
4146     df_md_bb_local_compute_process_def (bb_info,
4147                                         df_get_artificial_defs (bb_index),
4148                                         0);
4149 }
4150
4151 /* Compute local reaching def info for each basic block within BLOCKS.  */
4152
4153 static void
4154 df_md_local_compute (bitmap all_blocks)
4155 {
4156   unsigned int bb_index, df_bb_index;
4157   bitmap_iterator bi1, bi2;
4158   basic_block bb;
4159   bitmap_head *frontiers;
4160
4161   bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4162
4163   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4164     {
4165       df_md_bb_local_compute (bb_index);
4166     }
4167
4168   bitmap_clear (&seen_in_insn);
4169
4170   frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4171   FOR_ALL_BB_FN (bb, cfun)
4172     bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4173
4174   compute_dominance_frontiers (frontiers);
4175
4176   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
4177   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4178     {
4179       bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4180       EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4181         {
4182           basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4183           if (bitmap_bit_p (all_blocks, df_bb_index))
4184             bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4185                                  df_get_live_in (bb));
4186         }
4187     }
4188
4189   FOR_ALL_BB_FN (bb, cfun)
4190     bitmap_clear (&frontiers[bb->index]);
4191   free (frontiers);
4192 }
4193
4194
4195 /* Reset the global solution for recalculation.  */
4196
4197 static void
4198 df_md_reset (bitmap all_blocks)
4199 {
4200   unsigned int bb_index;
4201   bitmap_iterator bi;
4202
4203   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4204     {
4205       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4206       gcc_assert (bb_info);
4207       bitmap_clear (&bb_info->in);
4208       bitmap_clear (&bb_info->out);
4209     }
4210 }
4211
4212 static bool
4213 df_md_transfer_function (int bb_index)
4214 {
4215   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4216   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4217   bitmap in = &bb_info->in;
4218   bitmap out = &bb_info->out;
4219   bitmap gen = &bb_info->gen;
4220   bitmap kill = &bb_info->kill;
4221
4222   /* We need to use a scratch set here so that the value returned from this
4223      function invocation properly reflects whether the sets changed in a
4224      significant way; i.e. not just because the live set was anded in.  */
4225   bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4226
4227   /* Multiple definitions of a register are not relevant if it is not
4228      live.  Thus we trim the result to the places where it is live.  */
4229   bitmap_and_into (in, df_get_live_in (bb));
4230
4231   return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4232 }
4233
4234 /* Initialize the solution bit vectors for problem.  */
4235
4236 static void
4237 df_md_init (bitmap all_blocks)
4238 {
4239   unsigned int bb_index;
4240   bitmap_iterator bi;
4241
4242   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4243     {
4244       struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4245
4246       bitmap_copy (&bb_info->in, &bb_info->init);
4247       df_md_transfer_function (bb_index);
4248     }
4249 }
4250
4251 static void
4252 df_md_confluence_0 (basic_block bb)
4253 {
4254   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4255   bitmap_copy (&bb_info->in, &bb_info->init);
4256 }
4257
4258 /* In of target gets or of out of source.  */
4259
4260 static bool
4261 df_md_confluence_n (edge e)
4262 {
4263   bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4264   bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4265
4266   if (e->flags & EDGE_FAKE)
4267     return false;
4268
4269   if (e->flags & EDGE_EH)
4270     return bitmap_ior_and_compl_into (op1, op2,
4271                                       regs_invalidated_by_call_regset);
4272   else
4273     return bitmap_ior_into (op1, op2);
4274 }
4275
4276 /* Free all storage associated with the problem.  */
4277
4278 static void
4279 df_md_free (void)
4280 {
4281   struct df_md_problem_data *problem_data
4282     = (struct df_md_problem_data *) df_md->problem_data;
4283
4284   bitmap_obstack_release (&problem_data->md_bitmaps);
4285   free (problem_data);
4286   df_md->problem_data = NULL;
4287
4288   df_md->block_info_size = 0;
4289   free (df_md->block_info);
4290   df_md->block_info = NULL;
4291   free (df_md);
4292 }
4293
4294
4295 /* Debugging info at top of bb.  */
4296
4297 static void
4298 df_md_top_dump (basic_block bb, FILE *file)
4299 {
4300   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4301   if (!bb_info)
4302     return;
4303
4304   fprintf (file, ";; md  in  \t");
4305   df_print_regset (file, &bb_info->in);
4306   fprintf (file, ";; md  init  \t");
4307   df_print_regset (file, &bb_info->init);
4308   fprintf (file, ";; md  gen \t");
4309   df_print_regset (file, &bb_info->gen);
4310   fprintf (file, ";; md  kill \t");
4311   df_print_regset (file, &bb_info->kill);
4312 }
4313
4314 /* Debugging info at bottom of bb.  */
4315
4316 static void
4317 df_md_bottom_dump (basic_block bb, FILE *file)
4318 {
4319   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4320   if (!bb_info)
4321     return;
4322
4323   fprintf (file, ";; md  out \t");
4324   df_print_regset (file, &bb_info->out);
4325 }
4326
4327 static struct df_problem problem_MD =
4328 {
4329   DF_MD,                      /* Problem id.  */
4330   DF_FORWARD,                 /* Direction.  */
4331   df_md_alloc,                /* Allocate the problem specific data.  */
4332   df_md_reset,                /* Reset global information.  */
4333   df_md_free_bb_info,         /* Free basic block info.  */
4334   df_md_local_compute,        /* Local compute function.  */
4335   df_md_init,                 /* Init the solution specific data.  */
4336   df_worklist_dataflow,       /* Worklist solver.  */
4337   df_md_confluence_0,         /* Confluence operator 0.  */
4338   df_md_confluence_n,         /* Confluence operator n.  */
4339   df_md_transfer_function,    /* Transfer function.  */
4340   NULL,                       /* Finalize function.  */
4341   df_md_free,                 /* Free all of the problem information.  */
4342   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
4343   NULL,                       /* Debugging.  */
4344   df_md_top_dump,             /* Debugging start block.  */
4345   df_md_bottom_dump,          /* Debugging end block.  */
4346   NULL,                       /* Debugging start insn.  */
4347   NULL,                       /* Debugging end insn.  */
4348   NULL,                       /* Incremental solution verify start.  */
4349   NULL,                       /* Incremental solution verify end.  */
4350   NULL,                       /* Dependent problem.  */
4351   sizeof (struct df_md_bb_info),/* Size of entry of block_info array.  */
4352   TV_DF_MD,                   /* Timing variable.  */
4353   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
4354 };
4355
4356 /* Create a new MD instance and add it to the existing instance
4357    of DF.  */
4358
4359 void
4360 df_md_add_problem (void)
4361 {
4362   df_add_problem (&problem_MD);
4363 }
4364
4365
4366