contrib/gcc-8.0/gcc/df-scan.c

   1 /* Scanning of rtl for dataflow analysis.
   2    Copyright (C) 1999-2018 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 "backend.h"
  28 #include "target.h"
  29 #include "rtl.h"
  30 #include "tree.h"
  31 #include "df.h"
  32 #include "memmodel.h"
  33 #include "tm_p.h"
  34 #include "regs.h"
  35 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
  36 #include "dumpfile.h"
  37 #include "calls.h"
  38
  39
  40 /* The set of hard registers in eliminables[i].from. */
  41
  42 static HARD_REG_SET elim_reg_set;
  43
  44 /* Initialize ur_in and ur_out as if all hard registers were partially
  45    available.  */
  46
  47 struct df_collection_rec
  48 {
  49   auto_vec<df_ref, 128> def_vec;
  50   auto_vec<df_ref, 32> use_vec;
  51   auto_vec<df_ref, 32> eq_use_vec;
  52   auto_vec<df_mw_hardreg *, 32> mw_vec;
  53 };
  54
  55 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
  56                            rtx, rtx *,
  57                            basic_block, struct df_insn_info *,
  58                            enum df_ref_type, int ref_flags);
  59 static void df_def_record_1 (struct df_collection_rec *, rtx *,
  60                              basic_block, struct df_insn_info *,
  61                              int ref_flags);
  62 static void df_defs_record (struct df_collection_rec *, rtx,
  63                             basic_block, struct df_insn_info *,
  64                             int ref_flags);
  65 static void df_uses_record (struct df_collection_rec *,
  66                             rtx *, enum df_ref_type,
  67                             basic_block, struct df_insn_info *,
  68                             int ref_flags);
  69
  70 static void df_install_ref_incremental (df_ref);
  71 static void df_insn_refs_collect (struct df_collection_rec*,
  72                                   basic_block, struct df_insn_info *);
  73 static void df_canonize_collection_rec (struct df_collection_rec *);
  74
  75 static void df_get_regular_block_artificial_uses (bitmap);
  76 static void df_get_eh_block_artificial_uses (bitmap);
  77
  78 static void df_record_entry_block_defs (bitmap);
  79 static void df_record_exit_block_uses (bitmap);
  80 static void df_get_exit_block_use_set (bitmap);
  81 static void df_get_entry_block_def_set (bitmap);
  82 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
  83 static void df_ref_chain_delete_du_chain (df_ref);
  84 static void df_ref_chain_delete (df_ref);
  85
  86 static void df_refs_add_to_chains (struct df_collection_rec *,
  87                                    basic_block, rtx_insn *, unsigned int);
  88
  89 static bool df_insn_refs_verify (struct df_collection_rec *, basic_block,
  90                                  rtx_insn *, bool);
  91 static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap);
  92 static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
  93 static void df_install_ref (df_ref, struct df_reg_info *,
  94                             struct df_ref_info *, bool);
  95
  96 static int df_ref_compare (df_ref, df_ref);
  97 static int df_ref_ptr_compare (const void *, const void *);
  98 static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
  99 static int df_mw_ptr_compare (const void *, const void *);
 100
 101 static void df_insn_info_delete (unsigned int);
 102
 103 /* Indexed by hardware reg number, is true if that register is ever
 104    used in the current function.
 105
 106    In df-scan.c, this is set up to record the hard regs used
 107    explicitly.  Reload adds in the hard regs used for holding pseudo
 108    regs.  Final uses it to generate the code in the function prologue
 109    and epilogue to save and restore registers as needed.  */
 110
 111 static bool regs_ever_live[FIRST_PSEUDO_REGISTER];
 112
 113 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
 114 static const unsigned int copy_defs = 0x1;
 115 static const unsigned int copy_uses = 0x2;
 116 static const unsigned int copy_eq_uses = 0x4;
 117 static const unsigned int copy_mw = 0x8;
 118 static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses
 119 | copy_mw;
 120 \f
 121 /*----------------------------------------------------------------------------
 122    SCANNING DATAFLOW PROBLEM
 123
 124    There are several ways in which scanning looks just like the other
 125    dataflow problems.  It shares the all the mechanisms for local info
 126    as well as basic block info.  Where it differs is when and how often
 127    it gets run.  It also has no need for the iterative solver.
 128 ----------------------------------------------------------------------------*/
 129
 130 /* Problem data for the scanning dataflow function.  */
 131 struct df_scan_problem_data
 132 {
 133   object_allocator<df_base_ref> *ref_base_pool;
 134   object_allocator<df_artificial_ref> *ref_artificial_pool;
 135   object_allocator<df_regular_ref> *ref_regular_pool;
 136   object_allocator<df_insn_info> *insn_pool;
 137   object_allocator<df_reg_info> *reg_pool;
 138   object_allocator<df_mw_hardreg> *mw_reg_pool;
 139
 140   bitmap_obstack reg_bitmaps;
 141   bitmap_obstack insn_bitmaps;
 142 };
 143
 144 /* Internal function to shut down the scanning problem.  */
 145 static void
 146 df_scan_free_internal (void)
 147 {
 148   struct df_scan_problem_data *problem_data
 149     = (struct df_scan_problem_data *) df_scan->problem_data;
 150
 151   free (df->def_info.refs);
 152   free (df->def_info.begin);
 153   free (df->def_info.count);
 154   memset (&df->def_info, 0, (sizeof (struct df_ref_info)));
 155
 156   free (df->use_info.refs);
 157   free (df->use_info.begin);
 158   free (df->use_info.count);
 159   memset (&df->use_info, 0, (sizeof (struct df_ref_info)));
 160
 161   free (df->def_regs);
 162   df->def_regs = NULL;
 163   free (df->use_regs);
 164   df->use_regs = NULL;
 165   free (df->eq_use_regs);
 166   df->eq_use_regs = NULL;
 167   df->regs_size = 0;
 168   DF_REG_SIZE (df) = 0;
 169
 170   free (df->insns);
 171   df->insns = NULL;
 172   DF_INSN_SIZE () = 0;
 173
 174   free (df_scan->block_info);
 175   df_scan->block_info = NULL;
 176   df_scan->block_info_size = 0;
 177
 178   bitmap_clear (&df->hardware_regs_used);
 179   bitmap_clear (&df->regular_block_artificial_uses);
 180   bitmap_clear (&df->eh_block_artificial_uses);
 181   BITMAP_FREE (df->entry_block_defs);
 182   BITMAP_FREE (df->exit_block_uses);
 183   bitmap_clear (&df->insns_to_delete);
 184   bitmap_clear (&df->insns_to_rescan);
 185   bitmap_clear (&df->insns_to_notes_rescan);
 186
 187   delete problem_data->ref_base_pool;
 188   delete problem_data->ref_artificial_pool;
 189   delete problem_data->ref_regular_pool;
 190   delete problem_data->insn_pool;
 191   delete problem_data->reg_pool;
 192   delete problem_data->mw_reg_pool;
 193   bitmap_obstack_release (&problem_data->reg_bitmaps);
 194   bitmap_obstack_release (&problem_data->insn_bitmaps);
 195   free (df_scan->problem_data);
 196 }
 197
 198
 199 /* Free basic block info.  */
 200
 201 static void
 202 df_scan_free_bb_info (basic_block bb, void *vbb_info)
 203 {
 204   struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
 205   unsigned int bb_index = bb->index;
 206   rtx_insn *insn;
 207
 208   FOR_BB_INSNS (bb, insn)
 209     if (INSN_P (insn))
 210       df_insn_info_delete (INSN_UID (insn));
 211
 212   if (bb_index < df_scan->block_info_size)
 213     bb_info = df_scan_get_bb_info (bb_index);
 214
 215   /* Get rid of any artificial uses or defs.  */
 216   df_ref_chain_delete_du_chain (bb_info->artificial_defs);
 217   df_ref_chain_delete_du_chain (bb_info->artificial_uses);
 218   df_ref_chain_delete (bb_info->artificial_defs);
 219   df_ref_chain_delete (bb_info->artificial_uses);
 220   bb_info->artificial_defs = NULL;
 221   bb_info->artificial_uses = NULL;
 222 }
 223
 224
 225 /* Allocate the problem data for the scanning problem.  This should be
 226    called when the problem is created or when the entire function is to
 227    be rescanned.  */
 228 void
 229 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
 230 {
 231   struct df_scan_problem_data *problem_data;
 232   unsigned int insn_num = get_max_uid () + 1;
 233   basic_block bb;
 234
 235   /* Given the number of pools, this is really faster than tearing
 236      everything apart.  */
 237   if (df_scan->problem_data)
 238     df_scan_free_internal ();
 239
 240   problem_data = XNEW (struct df_scan_problem_data);
 241   df_scan->problem_data = problem_data;
 242   df_scan->computed = true;
 243
 244   problem_data->ref_base_pool = new object_allocator<df_base_ref>
 245     ("df_scan ref base");
 246   problem_data->ref_artificial_pool = new object_allocator<df_artificial_ref>
 247     ("df_scan ref artificial");
 248   problem_data->ref_regular_pool = new object_allocator<df_regular_ref>
 249     ("df_scan ref regular");
 250   problem_data->insn_pool = new object_allocator<df_insn_info>
 251     ("df_scan insn");
 252   problem_data->reg_pool = new object_allocator<df_reg_info>
 253     ("df_scan reg");
 254   problem_data->mw_reg_pool = new object_allocator<df_mw_hardreg>
 255     ("df_scan mw_reg");
 256
 257   bitmap_obstack_initialize (&problem_data->reg_bitmaps);
 258   bitmap_obstack_initialize (&problem_data->insn_bitmaps);
 259
 260   insn_num += insn_num / 4;
 261   df_grow_reg_info ();
 262
 263   df_grow_insn_info ();
 264   df_grow_bb_info (df_scan);
 265
 266   FOR_ALL_BB_FN (bb, cfun)
 267     {
 268       unsigned int bb_index = bb->index;
 269       struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
 270       bb_info->artificial_defs = NULL;
 271       bb_info->artificial_uses = NULL;
 272     }
 273
 274   bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps);
 275   bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps);
 276   bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps);
 277   df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 278   df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
 279   bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps);
 280   bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps);
 281   bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps);
 282   df_scan->optional_p = false;
 283 }
 284
 285
 286 /* Free all of the data associated with the scan problem.  */
 287
 288 static void
 289 df_scan_free (void)
 290 {
 291   if (df_scan->problem_data)
 292     df_scan_free_internal ();
 293
 294   if (df->blocks_to_analyze)
 295     {
 296       BITMAP_FREE (df->blocks_to_analyze);
 297       df->blocks_to_analyze = NULL;
 298     }
 299
 300   free (df_scan);
 301 }
 302
 303 /* Dump the preamble for DF_SCAN dump. */
 304 static void
 305 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED)
 306 {
 307   int i;
 308   int dcount = 0;
 309   int ucount = 0;
 310   int ecount = 0;
 311   int icount = 0;
 312   int ccount = 0;
 313   basic_block bb;
 314   rtx_insn *insn;
 315
 316   fprintf (file, ";;  invalidated by call \t");
 317   df_print_regset (file, regs_invalidated_by_call_regset);
 318   fprintf (file, ";;  hardware regs used \t");
 319   df_print_regset (file, &df->hardware_regs_used);
 320   fprintf (file, ";;  regular block artificial uses \t");
 321   df_print_regset (file, &df->regular_block_artificial_uses);
 322   fprintf (file, ";;  eh block artificial uses \t");
 323   df_print_regset (file, &df->eh_block_artificial_uses);
 324   fprintf (file, ";;  entry block defs \t");
 325   df_print_regset (file, df->entry_block_defs);
 326   fprintf (file, ";;  exit block uses \t");
 327   df_print_regset (file, df->exit_block_uses);
 328   fprintf (file, ";;  regs ever live \t");
 329   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 330     if (df_regs_ever_live_p (i))
 331       fprintf (file, " %d [%s]", i, reg_names[i]);
 332   fprintf (file, "\n;;  ref usage \t");
 333
 334   for (i = 0; i < (int)df->regs_inited; i++)
 335     if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i))
 336       {
 337         const char * sep = "";
 338
 339         fprintf (file, "r%d={", i);
 340         if (DF_REG_DEF_COUNT (i))
 341           {
 342             fprintf (file, "%dd", DF_REG_DEF_COUNT (i));
 343             sep = ",";
 344             dcount += DF_REG_DEF_COUNT (i);
 345           }
 346         if (DF_REG_USE_COUNT (i))
 347           {
 348             fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i));
 349             sep = ",";
 350             ucount += DF_REG_USE_COUNT (i);
 351           }
 352         if (DF_REG_EQ_USE_COUNT (i))
 353           {
 354             fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i));
 355             ecount += DF_REG_EQ_USE_COUNT (i);
 356           }
 357         fprintf (file, "} ");
 358       }
 359
 360   FOR_EACH_BB_FN (bb, cfun)
 361     FOR_BB_INSNS (bb, insn)
 362       if (INSN_P (insn))
 363         {
 364           if (CALL_P (insn))
 365             ccount++;
 366           else
 367             icount++;
 368         }
 369
 370   fprintf (file, "\n;;    total ref usage %d{%dd,%du,%de}"
 371                  " in %d{%d regular + %d call} insns.\n",
 372                  dcount + ucount + ecount, dcount, ucount, ecount,
 373                  icount + ccount, icount, ccount);
 374 }
 375
 376 /* Dump the bb_info for a given basic block. */
 377 static void
 378 df_scan_start_block (basic_block bb, FILE *file)
 379 {
 380   struct df_scan_bb_info *bb_info
 381     = df_scan_get_bb_info (bb->index);
 382
 383   if (bb_info)
 384     {
 385       fprintf (file, ";; bb %d artificial_defs: ", bb->index);
 386       df_refs_chain_dump (bb_info->artificial_defs, true, file);
 387       fprintf (file, "\n;; bb %d artificial_uses: ", bb->index);
 388       df_refs_chain_dump (bb_info->artificial_uses, true, file);
 389       fprintf (file, "\n");
 390     }
 391 #if 0
 392   {
 393     rtx_insn *insn;
 394     FOR_BB_INSNS (bb, insn)
 395       if (INSN_P (insn))
 396         df_insn_debug (insn, false, file);
 397   }
 398 #endif
 399 }
 400
 401 static const struct df_problem problem_SCAN =
 402 {
 403   DF_SCAN,                    /* Problem id.  */
 404   DF_NONE,                    /* Direction.  */
 405   df_scan_alloc,              /* Allocate the problem specific data.  */
 406   NULL,                       /* Reset global information.  */
 407   df_scan_free_bb_info,       /* Free basic block info.  */
 408   NULL,                       /* Local compute function.  */
 409   NULL,                       /* Init the solution specific data.  */
 410   NULL,                       /* Iterative solver.  */
 411   NULL,                       /* Confluence operator 0.  */
 412   NULL,                       /* Confluence operator n.  */
 413   NULL,                       /* Transfer function.  */
 414   NULL,                       /* Finalize function.  */
 415   df_scan_free,               /* Free all of the problem information.  */
 416   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
 417   df_scan_start_dump,         /* Debugging.  */
 418   df_scan_start_block,        /* Debugging start block.  */
 419   NULL,                       /* Debugging end block.  */
 420   NULL,                       /* Debugging start insn.  */
 421   NULL,                       /* Debugging end insn.  */
 422   NULL,                       /* Incremental solution verify start.  */
 423   NULL,                       /* Incremental solution verify end.  */
 424   NULL,                       /* Dependent problem.  */
 425   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
 426   TV_DF_SCAN,                 /* Timing variable.  */
 427   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
 428 };
 429
 430
 431 /* Create a new DATAFLOW instance and add it to an existing instance
 432    of DF.  The returned structure is what is used to get at the
 433    solution.  */
 434
 435 void
 436 df_scan_add_problem (void)
 437 {
 438   df_add_problem (&problem_SCAN);
 439 }
 440
 441 \f
 442 /*----------------------------------------------------------------------------
 443    Storage Allocation Utilities
 444 ----------------------------------------------------------------------------*/
 445
 446
 447 /* First, grow the reg_info information.  If the current size is less than
 448    the number of pseudos, grow to 25% more than the number of
 449    pseudos.
 450
 451    Second, assure that all of the slots up to max_reg_num have been
 452    filled with reg_info structures.  */
 453
 454 void
 455 df_grow_reg_info (void)
 456 {
 457   unsigned int max_reg = max_reg_num ();
 458   unsigned int new_size = max_reg;
 459   struct df_scan_problem_data *problem_data
 460     = (struct df_scan_problem_data *) df_scan->problem_data;
 461   unsigned int i;
 462
 463   if (df->regs_size < new_size)
 464     {
 465       new_size += new_size / 4;
 466       df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size);
 467       df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size);
 468       df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs,
 469                                     new_size);
 470       df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size);
 471       df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size);
 472       df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size);
 473       df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size);
 474       df->regs_size = new_size;
 475     }
 476
 477   for (i = df->regs_inited; i < max_reg; i++)
 478     {
 479       struct df_reg_info *reg_info;
 480
 481       // TODO
 482       reg_info = problem_data->reg_pool->allocate ();
 483       memset (reg_info, 0, sizeof (struct df_reg_info));
 484       df->def_regs[i] = reg_info;
 485       reg_info = problem_data->reg_pool->allocate ();
 486       memset (reg_info, 0, sizeof (struct df_reg_info));
 487       df->use_regs[i] = reg_info;
 488       reg_info = problem_data->reg_pool->allocate ();
 489       memset (reg_info, 0, sizeof (struct df_reg_info));
 490       df->eq_use_regs[i] = reg_info;
 491       df->def_info.begin[i] = 0;
 492       df->def_info.count[i] = 0;
 493       df->use_info.begin[i] = 0;
 494       df->use_info.count[i] = 0;
 495     }
 496
 497   df->regs_inited = max_reg;
 498 }
 499
 500
 501 /* Grow the ref information.  */
 502
 503 static void
 504 df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size)
 505 {
 506   if (ref_info->refs_size < new_size)
 507     {
 508       ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size);
 509       memset (ref_info->refs + ref_info->refs_size, 0,
 510               (new_size - ref_info->refs_size) *sizeof (df_ref));
 511       ref_info->refs_size = new_size;
 512     }
 513 }
 514
 515
 516 /* Check and grow the ref information if necessary.  This routine
 517    guarantees total_size + BITMAP_ADDEND amount of entries in refs
 518    array.  It updates ref_info->refs_size only and does not change
 519    ref_info->total_size.  */
 520
 521 static void
 522 df_check_and_grow_ref_info (struct df_ref_info *ref_info,
 523                             unsigned bitmap_addend)
 524 {
 525   if (ref_info->refs_size < ref_info->total_size + bitmap_addend)
 526     {
 527       int new_size = ref_info->total_size + bitmap_addend;
 528       new_size += ref_info->total_size / 4;
 529       df_grow_ref_info (ref_info, new_size);
 530     }
 531 }
 532
 533
 534 /* Grow the ref information.  If the current size is less than the
 535    number of instructions, grow to 25% more than the number of
 536    instructions.  */
 537
 538 void
 539 df_grow_insn_info (void)
 540 {
 541   unsigned int new_size = get_max_uid () + 1;
 542   if (DF_INSN_SIZE () < new_size)
 543     {
 544       new_size += new_size / 4;
 545       df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size);
 546       memset (df->insns + df->insns_size, 0,
 547               (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *));
 548       DF_INSN_SIZE () = new_size;
 549     }
 550 }
 551
 552
 553
 554 \f
 555 /*----------------------------------------------------------------------------
 556    PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
 557 ----------------------------------------------------------------------------*/
 558
 559 /* Rescan all of the block_to_analyze or all of the blocks in the
 560    function if df_set_blocks if blocks_to_analyze is NULL;  */
 561
 562 void
 563 df_scan_blocks (void)
 564 {
 565   basic_block bb;
 566
 567   df->def_info.ref_order = DF_REF_ORDER_NO_TABLE;
 568   df->use_info.ref_order = DF_REF_ORDER_NO_TABLE;
 569
 570   df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses);
 571   df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses);
 572
 573   bitmap_ior_into (&df->eh_block_artificial_uses,
 574                    &df->regular_block_artificial_uses);
 575
 576   /* ENTRY and EXIT blocks have special defs/uses.  */
 577   df_get_entry_block_def_set (df->entry_block_defs);
 578   df_record_entry_block_defs (df->entry_block_defs);
 579   df_get_exit_block_use_set (df->exit_block_uses);
 580   df_record_exit_block_uses (df->exit_block_uses);
 581   df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
 582   df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
 583
 584   /* Regular blocks */
 585   FOR_EACH_BB_FN (bb, cfun)
 586     {
 587       unsigned int bb_index = bb->index;
 588       df_bb_refs_record (bb_index, true);
 589     }
 590 }
 591
 592 /* Create new refs under address LOC within INSN.  This function is
 593    only used externally.  REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
 594    depending on whether LOC is inside PATTERN (INSN) or a note.  */
 595
 596 void
 597 df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags)
 598 {
 599   gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE));
 600   df_uses_record (NULL, loc, DF_REF_REG_USE,
 601                   BLOCK_FOR_INSN (insn),
 602                   DF_INSN_INFO_GET (insn),
 603                   ref_flags);
 604 }
 605
 606 static void
 607 df_install_ref_incremental (df_ref ref)
 608 {
 609   struct df_reg_info **reg_info;
 610   struct df_ref_info *ref_info;
 611   df_ref *ref_ptr;
 612   bool add_to_table;
 613
 614   rtx_insn *insn = DF_REF_INSN (ref);
 615   basic_block bb = BLOCK_FOR_INSN (insn);
 616
 617   if (DF_REF_REG_DEF_P (ref))
 618     {
 619       reg_info = df->def_regs;
 620       ref_info = &df->def_info;
 621       ref_ptr = &DF_INSN_DEFS (insn);
 622       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
 623     }
 624   else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
 625     {
 626       reg_info = df->eq_use_regs;
 627       ref_info = &df->use_info;
 628       ref_ptr = &DF_INSN_EQ_USES (insn);
 629       switch (ref_info->ref_order)
 630         {
 631         case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 632         case DF_REF_ORDER_BY_REG_WITH_NOTES:
 633         case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 634           add_to_table = true;
 635           break;
 636         default:
 637           add_to_table = false;
 638           break;
 639         }
 640     }
 641   else
 642     {
 643       reg_info = df->use_regs;
 644       ref_info = &df->use_info;
 645       ref_ptr = &DF_INSN_USES (insn);
 646       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
 647     }
 648
 649   /* Do not add if ref is not in the right blocks.  */
 650   if (add_to_table && df->analyze_subset)
 651     add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
 652
 653   df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table);
 654
 655   if (add_to_table)
 656     switch (ref_info->ref_order)
 657       {
 658       case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 659       case DF_REF_ORDER_BY_REG_WITH_NOTES:
 660       case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 661         ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
 662         break;
 663       default:
 664         ref_info->ref_order = DF_REF_ORDER_UNORDERED;
 665         break;
 666       }
 667
 668   while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
 669     ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
 670
 671   DF_REF_NEXT_LOC (ref) = *ref_ptr;
 672   *ref_ptr = ref;
 673
 674 #if 0
 675   if (dump_file)
 676     {
 677       fprintf (dump_file, "adding ref ");
 678       df_ref_debug (ref, dump_file);
 679     }
 680 #endif
 681   /* By adding the ref directly, df_insn_rescan my not find any
 682      differences even though the block will have changed.  So we need
 683      to mark the block dirty ourselves.  */
 684   if (!DEBUG_INSN_P (DF_REF_INSN (ref)))
 685     df_set_bb_dirty (bb);
 686 }
 687
 688
 689 \f
 690 /*----------------------------------------------------------------------------
 691    UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
 692 ----------------------------------------------------------------------------*/
 693
 694 static void
 695 df_free_ref (df_ref ref)
 696 {
 697   struct df_scan_problem_data *problem_data
 698     = (struct df_scan_problem_data *) df_scan->problem_data;
 699
 700   switch (DF_REF_CLASS (ref))
 701     {
 702     case DF_REF_BASE:
 703       problem_data->ref_base_pool->remove ((df_base_ref *) (ref));
 704       break;
 705
 706     case DF_REF_ARTIFICIAL:
 707       problem_data->ref_artificial_pool->remove
 708         ((df_artificial_ref *) (ref));
 709       break;
 710
 711     case DF_REF_REGULAR:
 712       problem_data->ref_regular_pool->remove
 713         ((df_regular_ref *) (ref));
 714       break;
 715     }
 716 }
 717
 718
 719 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
 720    Also delete the def-use or use-def chain if it exists.  */
 721
 722 static void
 723 df_reg_chain_unlink (df_ref ref)
 724 {
 725   df_ref next = DF_REF_NEXT_REG (ref);
 726   df_ref prev = DF_REF_PREV_REG (ref);
 727   int id = DF_REF_ID (ref);
 728   struct df_reg_info *reg_info;
 729   df_ref *refs = NULL;
 730
 731   if (DF_REF_REG_DEF_P (ref))
 732     {
 733       int regno = DF_REF_REGNO (ref);
 734       reg_info = DF_REG_DEF_GET (regno);
 735       refs = df->def_info.refs;
 736     }
 737   else
 738     {
 739       if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
 740         {
 741           reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
 742           switch (df->use_info.ref_order)
 743             {
 744             case DF_REF_ORDER_UNORDERED_WITH_NOTES:
 745             case DF_REF_ORDER_BY_REG_WITH_NOTES:
 746             case DF_REF_ORDER_BY_INSN_WITH_NOTES:
 747               refs = df->use_info.refs;
 748               break;
 749             default:
 750               break;
 751             }
 752         }
 753       else
 754         {
 755           reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
 756           refs = df->use_info.refs;
 757         }
 758     }
 759
 760   if (refs)
 761     {
 762       if (df->analyze_subset)
 763         {
 764           if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref)))
 765             refs[id] = NULL;
 766         }
 767       else
 768         refs[id] = NULL;
 769     }
 770
 771   /* Delete any def-use or use-def chains that start here. It is
 772      possible that there is trash in this field.  This happens for
 773      insns that have been deleted when rescanning has been deferred
 774      and the chain problem has also been deleted.  The chain tear down
 775      code skips deleted insns.  */
 776   if (df_chain && DF_REF_CHAIN (ref))
 777     df_chain_unlink (ref);
 778
 779   reg_info->n_refs--;
 780   if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE))
 781     {
 782       gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
 783       df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
 784     }
 785
 786   /* Unlink from the reg chain.  If there is no prev, this is the
 787      first of the list.  If not, just join the next and prev.  */
 788   if (prev)
 789     DF_REF_NEXT_REG (prev) = next;
 790   else
 791     {
 792       gcc_assert (reg_info->reg_chain == ref);
 793       reg_info->reg_chain = next;
 794     }
 795   if (next)
 796     DF_REF_PREV_REG (next) = prev;
 797
 798   df_free_ref (ref);
 799 }
 800
 801 /* Initialize INSN_INFO to describe INSN.  */
 802
 803 static void
 804 df_insn_info_init_fields (df_insn_info *insn_info, rtx_insn *insn)
 805 {
 806   memset (insn_info, 0, sizeof (struct df_insn_info));
 807   insn_info->insn = insn;
 808 }
 809
 810 /* Create the insn record for INSN.  If there was one there, zero it
 811    out.  */
 812
 813 struct df_insn_info *
 814 df_insn_create_insn_record (rtx_insn *insn)
 815 {
 816   struct df_scan_problem_data *problem_data
 817     = (struct df_scan_problem_data *) df_scan->problem_data;
 818   struct df_insn_info *insn_rec;
 819
 820   df_grow_insn_info ();
 821   insn_rec = DF_INSN_INFO_GET (insn);
 822   if (!insn_rec)
 823     {
 824       insn_rec = problem_data->insn_pool->allocate ();
 825       DF_INSN_INFO_SET (insn, insn_rec);
 826     }
 827   df_insn_info_init_fields (insn_rec, insn);
 828   return insn_rec;
 829 }
 830
 831
 832 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain.  */
 833
 834 static void
 835 df_ref_chain_delete_du_chain (df_ref ref)
 836 {
 837   for (; ref; ref = DF_REF_NEXT_LOC (ref))
 838     /* CHAIN is allocated by DF_CHAIN. So make sure to
 839        pass df_scan instance for the problem.  */
 840     if (DF_REF_CHAIN (ref))
 841       df_chain_unlink (ref);
 842 }
 843
 844
 845 /* Delete all refs in the ref chain.  */
 846
 847 static void
 848 df_ref_chain_delete (df_ref ref)
 849 {
 850   df_ref next;
 851   for (; ref; ref = next)
 852     {
 853       next = DF_REF_NEXT_LOC (ref);
 854       df_reg_chain_unlink (ref);
 855     }
 856 }
 857
 858
 859 /* Delete the hardreg chain.  */
 860
 861 static void
 862 df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
 863 {
 864   struct df_scan_problem_data *problem_data
 865     = (struct df_scan_problem_data *) df_scan->problem_data;
 866   df_mw_hardreg *next;
 867
 868   for (; hardregs; hardregs = next)
 869     {
 870       next = DF_MWS_NEXT (hardregs);
 871       problem_data->mw_reg_pool->remove (hardregs);
 872     }
 873 }
 874
 875 /* Remove the contents of INSN_INFO (but don't free INSN_INFO itself).  */
 876
 877 static void
 878 df_insn_info_free_fields (df_insn_info *insn_info)
 879 {
 880   /* In general, notes do not have the insn_info fields
 881      initialized.  However, combine deletes insns by changing them
 882      to notes.  How clever.  So we cannot just check if it is a
 883      valid insn before short circuiting this code, we need to see
 884      if we actually initialized it.  */
 885   df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
 886
 887   if (df_chain)
 888     {
 889       df_ref_chain_delete_du_chain (insn_info->defs);
 890       df_ref_chain_delete_du_chain (insn_info->uses);
 891       df_ref_chain_delete_du_chain (insn_info->eq_uses);
 892     }
 893
 894   df_ref_chain_delete (insn_info->defs);
 895   df_ref_chain_delete (insn_info->uses);
 896   df_ref_chain_delete (insn_info->eq_uses);
 897 }
 898
 899 /* Delete all of the refs information from the insn with UID.
 900    Internal helper for df_insn_delete, df_insn_rescan, and other
 901    df-scan routines that don't have to work in deferred mode
 902    and do not have to mark basic blocks for re-processing.  */
 903
 904 static void
 905 df_insn_info_delete (unsigned int uid)
 906 {
 907   struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
 908
 909   bitmap_clear_bit (&df->insns_to_delete, uid);
 910   bitmap_clear_bit (&df->insns_to_rescan, uid);
 911   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
 912   if (insn_info)
 913     {
 914       struct df_scan_problem_data *problem_data
 915         = (struct df_scan_problem_data *) df_scan->problem_data;
 916
 917       df_insn_info_free_fields (insn_info);
 918       problem_data->insn_pool->remove (insn_info);
 919       DF_INSN_UID_SET (uid, NULL);
 920     }
 921 }
 922
 923 /* Delete all of the refs information from INSN, either right now
 924    or marked for later in deferred mode.  */
 925
 926 void
 927 df_insn_delete (rtx_insn *insn)
 928 {
 929   unsigned int uid;
 930   basic_block bb;
 931
 932   gcc_checking_assert (INSN_P (insn));
 933
 934   if (!df)
 935     return;
 936
 937   uid = INSN_UID (insn);
 938   bb = BLOCK_FOR_INSN (insn);
 939
 940   /* ??? bb can be NULL after pass_free_cfg.  At that point, DF should
 941      not exist anymore (as mentioned in df-core.c: "The only requirement
 942      [for DF] is that there be a correct control flow graph."  Clearly
 943      that isn't the case after pass_free_cfg.  But DF is freed much later
 944      because some back-ends want to use DF info even though the CFG is
 945      already gone.  It's not clear to me whether that is safe, actually.
 946      In any case, we expect BB to be non-NULL at least up to register
 947      allocation, so disallow a non-NULL BB up to there.  Not perfect
 948      but better than nothing...  */
 949   gcc_checking_assert (bb != NULL || reload_completed);
 950
 951   df_grow_bb_info (df_scan);
 952   df_grow_reg_info ();
 953
 954   /* The block must be marked as dirty now, rather than later as in
 955      df_insn_rescan and df_notes_rescan because it may not be there at
 956      rescanning time and the mark would blow up.
 957      DEBUG_INSNs do not make a block's data flow solution dirty (at
 958      worst the LUIDs are no longer contiguous).  */
 959   if (bb != NULL && NONDEBUG_INSN_P (insn))
 960     df_set_bb_dirty (bb);
 961
 962   /* The client has deferred rescanning.  */
 963   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
 964     {
 965       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
 966       if (insn_info)
 967         {
 968           bitmap_clear_bit (&df->insns_to_rescan, uid);
 969           bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
 970           bitmap_set_bit (&df->insns_to_delete, uid);
 971         }
 972       if (dump_file)
 973         fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid);
 974       return;
 975     }
 976
 977   if (dump_file)
 978     fprintf (dump_file, "deleting insn with uid = %d.\n", uid);
 979
 980   df_insn_info_delete (uid);
 981 }
 982
 983
 984 /* Free all of the refs and the mw_hardregs in COLLECTION_REC.  */
 985
 986 static void
 987 df_free_collection_rec (struct df_collection_rec *collection_rec)
 988 {
 989   unsigned int ix;
 990   struct df_scan_problem_data *problem_data
 991     = (struct df_scan_problem_data *) df_scan->problem_data;
 992   df_ref ref;
 993   struct df_mw_hardreg *mw;
 994
 995   FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
 996     df_free_ref (ref);
 997   FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref)
 998     df_free_ref (ref);
 999   FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref)
1000     df_free_ref (ref);
1001   FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw)
1002     problem_data->mw_reg_pool->remove (mw);
1003
1004   collection_rec->def_vec.release ();
1005   collection_rec->use_vec.release ();
1006   collection_rec->eq_use_vec.release ();
1007   collection_rec->mw_vec.release ();
1008 }
1009
1010 /* Rescan INSN.  Return TRUE if the rescanning produced any changes.  */
1011
1012 bool
1013 df_insn_rescan (rtx_insn *insn)
1014 {
1015   unsigned int uid = INSN_UID (insn);
1016   struct df_insn_info *insn_info = NULL;
1017   basic_block bb = BLOCK_FOR_INSN (insn);
1018   struct df_collection_rec collection_rec;
1019
1020   if ((!df) || (!INSN_P (insn)))
1021     return false;
1022
1023   if (!bb)
1024     {
1025       if (dump_file)
1026         fprintf (dump_file, "no bb for insn with uid = %d.\n", uid);
1027       return false;
1028     }
1029
1030   /* The client has disabled rescanning and plans to do it itself.  */
1031   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1032     return false;
1033
1034   df_grow_bb_info (df_scan);
1035   df_grow_reg_info ();
1036
1037   insn_info = DF_INSN_UID_SAFE_GET (uid);
1038
1039   /* The client has deferred rescanning.  */
1040   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1041     {
1042       if (!insn_info)
1043         {
1044           insn_info = df_insn_create_insn_record (insn);
1045           insn_info->defs = 0;
1046           insn_info->uses = 0;
1047           insn_info->eq_uses = 0;
1048           insn_info->mw_hardregs = 0;
1049         }
1050       if (dump_file)
1051         fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
1052
1053       bitmap_clear_bit (&df->insns_to_delete, uid);
1054       bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1055       bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn));
1056       return false;
1057     }
1058
1059   bitmap_clear_bit (&df->insns_to_delete, uid);
1060   bitmap_clear_bit (&df->insns_to_rescan, uid);
1061   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1062   if (insn_info)
1063     {
1064       int luid;
1065       bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false);
1066       /* If there's no change, return false. */
1067       if (the_same)
1068         {
1069           df_free_collection_rec (&collection_rec);
1070           if (dump_file)
1071             fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid);
1072           return false;
1073         }
1074       if (dump_file)
1075         fprintf (dump_file, "rescanning insn with uid = %d.\n", uid);
1076
1077       /* There's change - we need to delete the existing info.
1078          Since the insn isn't moved, we can salvage its LUID.  */
1079       luid = DF_INSN_LUID (insn);
1080       df_insn_info_free_fields (insn_info);
1081       df_insn_info_init_fields (insn_info, insn);
1082       DF_INSN_LUID (insn) = luid;
1083     }
1084   else
1085     {
1086       struct df_insn_info *insn_info = df_insn_create_insn_record (insn);
1087       df_insn_refs_collect (&collection_rec, bb, insn_info);
1088       if (dump_file)
1089         fprintf (dump_file, "scanning new insn with uid = %d.\n", uid);
1090     }
1091
1092   df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
1093   if (!DEBUG_INSN_P (insn))
1094     df_set_bb_dirty (bb);
1095
1096   return true;
1097 }
1098
1099 /* Same as df_insn_rescan, but don't mark the basic block as
1100    dirty.  */
1101
1102 bool
1103 df_insn_rescan_debug_internal (rtx_insn *insn)
1104 {
1105   unsigned int uid = INSN_UID (insn);
1106   struct df_insn_info *insn_info;
1107
1108   gcc_assert (DEBUG_INSN_P (insn)
1109               && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)));
1110
1111   if (!df)
1112     return false;
1113
1114   insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1115   if (!insn_info)
1116     return false;
1117
1118   if (dump_file)
1119     fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid);
1120
1121   bitmap_clear_bit (&df->insns_to_delete, uid);
1122   bitmap_clear_bit (&df->insns_to_rescan, uid);
1123   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1124
1125   if (insn_info->defs == 0
1126       && insn_info->uses == 0
1127       && insn_info->eq_uses == 0
1128       && insn_info->mw_hardregs == 0)
1129     return false;
1130
1131   df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
1132
1133   if (df_chain)
1134     {
1135       df_ref_chain_delete_du_chain (insn_info->defs);
1136       df_ref_chain_delete_du_chain (insn_info->uses);
1137       df_ref_chain_delete_du_chain (insn_info->eq_uses);
1138     }
1139
1140   df_ref_chain_delete (insn_info->defs);
1141   df_ref_chain_delete (insn_info->uses);
1142   df_ref_chain_delete (insn_info->eq_uses);
1143
1144   insn_info->defs = 0;
1145   insn_info->uses = 0;
1146   insn_info->eq_uses = 0;
1147   insn_info->mw_hardregs = 0;
1148
1149   return true;
1150 }
1151
1152
1153 /* Rescan all of the insns in the function.  Note that the artificial
1154    uses and defs are not touched.  This function will destroy def-use
1155    or use-def chains.  */
1156
1157 void
1158 df_insn_rescan_all (void)
1159 {
1160   bool no_insn_rescan = false;
1161   bool defer_insn_rescan = false;
1162   basic_block bb;
1163   bitmap_iterator bi;
1164   unsigned int uid;
1165
1166   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1167     {
1168       df_clear_flags (DF_NO_INSN_RESCAN);
1169       no_insn_rescan = true;
1170     }
1171
1172   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1173     {
1174       df_clear_flags (DF_DEFER_INSN_RESCAN);
1175       defer_insn_rescan = true;
1176     }
1177
1178   auto_bitmap tmp (&df_bitmap_obstack);
1179   bitmap_copy (tmp, &df->insns_to_delete);
1180   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1181     {
1182       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1183       if (insn_info)
1184         df_insn_info_delete (uid);
1185     }
1186
1187   bitmap_clear (&df->insns_to_delete);
1188   bitmap_clear (&df->insns_to_rescan);
1189   bitmap_clear (&df->insns_to_notes_rescan);
1190
1191   FOR_EACH_BB_FN (bb, cfun)
1192     {
1193       rtx_insn *insn;
1194       FOR_BB_INSNS (bb, insn)
1195         {
1196           df_insn_rescan (insn);
1197         }
1198     }
1199
1200   if (no_insn_rescan)
1201     df_set_flags (DF_NO_INSN_RESCAN);
1202   if (defer_insn_rescan)
1203     df_set_flags (DF_DEFER_INSN_RESCAN);
1204 }
1205
1206
1207 /* Process all of the deferred rescans or deletions.  */
1208
1209 void
1210 df_process_deferred_rescans (void)
1211 {
1212   bool no_insn_rescan = false;
1213   bool defer_insn_rescan = false;
1214   bitmap_iterator bi;
1215   unsigned int uid;
1216
1217   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1218     {
1219       df_clear_flags (DF_NO_INSN_RESCAN);
1220       no_insn_rescan = true;
1221     }
1222
1223   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1224     {
1225       df_clear_flags (DF_DEFER_INSN_RESCAN);
1226       defer_insn_rescan = true;
1227     }
1228
1229   if (dump_file)
1230     fprintf (dump_file, "starting the processing of deferred insns\n");
1231
1232   auto_bitmap tmp (&df_bitmap_obstack);
1233   bitmap_copy (tmp, &df->insns_to_delete);
1234   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1235     {
1236       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1237       if (insn_info)
1238         df_insn_info_delete (uid);
1239     }
1240
1241   bitmap_copy (tmp, &df->insns_to_rescan);
1242   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1243     {
1244       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1245       if (insn_info)
1246         df_insn_rescan (insn_info->insn);
1247     }
1248
1249   bitmap_copy (tmp, &df->insns_to_notes_rescan);
1250   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, uid, bi)
1251     {
1252       struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid);
1253       if (insn_info)
1254         df_notes_rescan (insn_info->insn);
1255     }
1256
1257   if (dump_file)
1258     fprintf (dump_file, "ending the processing of deferred insns\n");
1259
1260   bitmap_clear (&df->insns_to_delete);
1261   bitmap_clear (&df->insns_to_rescan);
1262   bitmap_clear (&df->insns_to_notes_rescan);
1263
1264   if (no_insn_rescan)
1265     df_set_flags (DF_NO_INSN_RESCAN);
1266   if (defer_insn_rescan)
1267     df_set_flags (DF_DEFER_INSN_RESCAN);
1268
1269   /* If someone changed regs_ever_live during this pass, fix up the
1270      entry and exit blocks.  */
1271   if (df->redo_entry_and_exit)
1272     {
1273       df_update_entry_exit_and_calls ();
1274       df->redo_entry_and_exit = false;
1275     }
1276 }
1277
1278
1279 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1280    the uses if INCLUDE_USES. Include the eq_uses if
1281    INCLUDE_EQ_USES.  */
1282
1283 static unsigned int
1284 df_count_refs (bool include_defs, bool include_uses,
1285                bool include_eq_uses)
1286 {
1287   unsigned int regno;
1288   int size = 0;
1289   unsigned int m = df->regs_inited;
1290
1291   for (regno = 0; regno < m; regno++)
1292     {
1293       if (include_defs)
1294         size += DF_REG_DEF_COUNT (regno);
1295       if (include_uses)
1296         size += DF_REG_USE_COUNT (regno);
1297       if (include_eq_uses)
1298         size += DF_REG_EQ_USE_COUNT (regno);
1299     }
1300   return size;
1301 }
1302
1303
1304 /* Take build ref table for either the uses or defs from the reg-use
1305    or reg-def chains.  This version processes the refs in reg order
1306    which is likely to be best if processing the whole function.  */
1307
1308 static void
1309 df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info,
1310                                   bool include_defs,
1311                                   bool include_uses,
1312                                   bool include_eq_uses)
1313 {
1314   unsigned int m = df->regs_inited;
1315   unsigned int regno;
1316   unsigned int offset = 0;
1317   unsigned int start;
1318
1319   if (df->changeable_flags & DF_NO_HARD_REGS)
1320     {
1321       start = FIRST_PSEUDO_REGISTER;
1322       memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1323       memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER);
1324     }
1325   else
1326     start = 0;
1327
1328   ref_info->total_size
1329     = df_count_refs (include_defs, include_uses, include_eq_uses);
1330
1331   df_check_and_grow_ref_info (ref_info, 1);
1332
1333   for (regno = start; regno < m; regno++)
1334     {
1335       int count = 0;
1336       ref_info->begin[regno] = offset;
1337       if (include_defs)
1338         {
1339           df_ref ref = DF_REG_DEF_CHAIN (regno);
1340           while (ref)
1341             {
1342               ref_info->refs[offset] = ref;
1343               DF_REF_ID (ref) = offset++;
1344               count++;
1345               ref = DF_REF_NEXT_REG (ref);
1346               gcc_checking_assert (offset < ref_info->refs_size);
1347             }
1348         }
1349       if (include_uses)
1350         {
1351           df_ref ref = DF_REG_USE_CHAIN (regno);
1352           while (ref)
1353             {
1354               ref_info->refs[offset] = ref;
1355               DF_REF_ID (ref) = offset++;
1356               count++;
1357               ref = DF_REF_NEXT_REG (ref);
1358               gcc_checking_assert (offset < ref_info->refs_size);
1359             }
1360         }
1361       if (include_eq_uses)
1362         {
1363           df_ref ref = DF_REG_EQ_USE_CHAIN (regno);
1364           while (ref)
1365             {
1366               ref_info->refs[offset] = ref;
1367               DF_REF_ID (ref) = offset++;
1368               count++;
1369               ref = DF_REF_NEXT_REG (ref);
1370               gcc_checking_assert (offset < ref_info->refs_size);
1371             }
1372         }
1373       ref_info->count[regno] = count;
1374     }
1375
1376   /* The bitmap size is not decremented when refs are deleted.  So
1377      reset it now that we have squished out all of the empty
1378      slots.  */
1379   ref_info->table_size = offset;
1380 }
1381
1382
1383 /* Take build ref table for either the uses or defs from the reg-use
1384    or reg-def chains.  This version processes the refs in insn order
1385    which is likely to be best if processing some segment of the
1386    function.  */
1387
1388 static void
1389 df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info,
1390                                    bool include_defs,
1391                                    bool include_uses,
1392                                    bool include_eq_uses)
1393 {
1394   bitmap_iterator bi;
1395   unsigned int bb_index;
1396   unsigned int m = df->regs_inited;
1397   unsigned int offset = 0;
1398   unsigned int r;
1399   unsigned int start
1400     = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0;
1401
1402   memset (ref_info->begin, 0, sizeof (int) * df->regs_inited);
1403   memset (ref_info->count, 0, sizeof (int) * df->regs_inited);
1404
1405   ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1406   df_check_and_grow_ref_info (ref_info, 1);
1407
1408   EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1409     {
1410       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1411       rtx_insn *insn;
1412       df_ref def, use;
1413
1414       if (include_defs)
1415         FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1416           {
1417             unsigned int regno = DF_REF_REGNO (def);
1418             ref_info->count[regno]++;
1419           }
1420       if (include_uses)
1421         FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1422           {
1423             unsigned int regno = DF_REF_REGNO (use);
1424             ref_info->count[regno]++;
1425           }
1426
1427       FOR_BB_INSNS (bb, insn)
1428         {
1429           if (INSN_P (insn))
1430             {
1431               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1432
1433               if (include_defs)
1434                 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1435                   {
1436                     unsigned int regno = DF_REF_REGNO (def);
1437                     ref_info->count[regno]++;
1438                   }
1439               if (include_uses)
1440                 FOR_EACH_INSN_INFO_USE (use, insn_info)
1441                   {
1442                     unsigned int regno = DF_REF_REGNO (use);
1443                     ref_info->count[regno]++;
1444                   }
1445               if (include_eq_uses)
1446                 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1447                   {
1448                     unsigned int regno = DF_REF_REGNO (use);
1449                     ref_info->count[regno]++;
1450                   }
1451             }
1452         }
1453     }
1454
1455   for (r = start; r < m; r++)
1456     {
1457       ref_info->begin[r] = offset;
1458       offset += ref_info->count[r];
1459       ref_info->count[r] = 0;
1460     }
1461
1462   EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
1463     {
1464       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1465       rtx_insn *insn;
1466       df_ref def, use;
1467
1468       if (include_defs)
1469         FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1470           {
1471             unsigned int regno = DF_REF_REGNO (def);
1472             if (regno >= start)
1473               {
1474                 unsigned int id
1475                   = ref_info->begin[regno] + ref_info->count[regno]++;
1476                 DF_REF_ID (def) = id;
1477                 ref_info->refs[id] = def;
1478               }
1479           }
1480       if (include_uses)
1481         FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1482           {
1483             unsigned int regno = DF_REF_REGNO (def);
1484             if (regno >= start)
1485               {
1486                 unsigned int id
1487                   = ref_info->begin[regno] + ref_info->count[regno]++;
1488                 DF_REF_ID (use) = id;
1489                 ref_info->refs[id] = use;
1490               }
1491           }
1492
1493       FOR_BB_INSNS (bb, insn)
1494         {
1495           if (INSN_P (insn))
1496             {
1497               struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1498
1499               if (include_defs)
1500                 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1501                   {
1502                     unsigned int regno = DF_REF_REGNO (def);
1503                     if (regno >= start)
1504                       {
1505                         unsigned int id
1506                           = ref_info->begin[regno] + ref_info->count[regno]++;
1507                         DF_REF_ID (def) = id;
1508                         ref_info->refs[id] = def;
1509                       }
1510                   }
1511               if (include_uses)
1512                 FOR_EACH_INSN_INFO_USE (use, insn_info)
1513                   {
1514                     unsigned int regno = DF_REF_REGNO (use);
1515                     if (regno >= start)
1516                       {
1517                         unsigned int id
1518                           = ref_info->begin[regno] + ref_info->count[regno]++;
1519                         DF_REF_ID (use) = id;
1520                         ref_info->refs[id] = use;
1521                       }
1522                   }
1523               if (include_eq_uses)
1524                 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1525                   {
1526                     unsigned int regno = DF_REF_REGNO (use);
1527                     if (regno >= start)
1528                       {
1529                         unsigned int id
1530                           = ref_info->begin[regno] + ref_info->count[regno]++;
1531                         DF_REF_ID (use) = id;
1532                         ref_info->refs[id] = use;
1533                       }
1534                   }
1535             }
1536         }
1537     }
1538
1539   /* The bitmap size is not decremented when refs are deleted.  So
1540      reset it now that we have squished out all of the empty
1541      slots.  */
1542
1543   ref_info->table_size = offset;
1544 }
1545
1546 /* Take build ref table for either the uses or defs from the reg-use
1547    or reg-def chains.  */
1548
1549 static void
1550 df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
1551                            bool include_defs,
1552                            bool include_uses,
1553                            bool include_eq_uses)
1554 {
1555   if (df->analyze_subset)
1556     df_reorganize_refs_by_reg_by_insn (ref_info, include_defs,
1557                                        include_uses, include_eq_uses);
1558   else
1559     df_reorganize_refs_by_reg_by_reg (ref_info, include_defs,
1560                                        include_uses, include_eq_uses);
1561 }
1562
1563
1564 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET.  */
1565 static unsigned int
1566 df_add_refs_to_table (unsigned int offset,
1567                       struct df_ref_info *ref_info,
1568                       df_ref ref)
1569 {
1570   for (; ref; ref = DF_REF_NEXT_LOC (ref))
1571     if (!(df->changeable_flags & DF_NO_HARD_REGS)
1572         || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
1573       {
1574         ref_info->refs[offset] = ref;
1575         DF_REF_ID (ref) = offset++;
1576       }
1577   return offset;
1578 }
1579
1580
1581 /* Count the number of refs in all of the insns of BB. Include the
1582    defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1583    eq_uses if INCLUDE_EQ_USES.  */
1584
1585 static unsigned int
1586 df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset,
1587                                struct df_ref_info *ref_info,
1588                                bool include_defs, bool include_uses,
1589                                bool include_eq_uses)
1590 {
1591   rtx_insn *insn;
1592
1593   if (include_defs)
1594     offset = df_add_refs_to_table (offset, ref_info,
1595                                    df_get_artificial_defs (bb->index));
1596   if (include_uses)
1597     offset = df_add_refs_to_table (offset, ref_info,
1598                                    df_get_artificial_uses (bb->index));
1599
1600   FOR_BB_INSNS (bb, insn)
1601     if (INSN_P (insn))
1602       {
1603         unsigned int uid = INSN_UID (insn);
1604         if (include_defs)
1605           offset = df_add_refs_to_table (offset, ref_info,
1606                                          DF_INSN_UID_DEFS (uid));
1607         if (include_uses)
1608           offset = df_add_refs_to_table (offset, ref_info,
1609                                          DF_INSN_UID_USES (uid));
1610         if (include_eq_uses)
1611           offset = df_add_refs_to_table (offset, ref_info,
1612                                          DF_INSN_UID_EQ_USES (uid));
1613       }
1614   return offset;
1615 }
1616
1617
1618 /* Organize the refs by insn into the table in REF_INFO.  If
1619    blocks_to_analyze is defined, use that set, otherwise the entire
1620    program.  Include the defs if INCLUDE_DEFS. Include the uses if
1621    INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES.  */
1622
1623 static void
1624 df_reorganize_refs_by_insn (struct df_ref_info *ref_info,
1625                             bool include_defs, bool include_uses,
1626                             bool include_eq_uses)
1627 {
1628   basic_block bb;
1629   unsigned int offset = 0;
1630
1631   ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses);
1632   df_check_and_grow_ref_info (ref_info, 1);
1633   if (df->blocks_to_analyze)
1634     {
1635       bitmap_iterator bi;
1636       unsigned int index;
1637
1638       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi)
1639         {
1640           offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun,
1641                                                                       index),
1642                                                   offset, ref_info,
1643                                                   include_defs, include_uses,
1644                                                   include_eq_uses);
1645         }
1646
1647       ref_info->table_size = offset;
1648     }
1649   else
1650     {
1651       FOR_ALL_BB_FN (bb, cfun)
1652         offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info,
1653                                                 include_defs, include_uses,
1654                                                 include_eq_uses);
1655       ref_info->table_size = offset;
1656     }
1657 }
1658
1659
1660 /* If the use refs in DF are not organized, reorganize them.  */
1661
1662 void
1663 df_maybe_reorganize_use_refs (enum df_ref_order order)
1664 {
1665   if (order == df->use_info.ref_order)
1666     return;
1667
1668   switch (order)
1669     {
1670     case DF_REF_ORDER_BY_REG:
1671       df_reorganize_refs_by_reg (&df->use_info, false, true, false);
1672       break;
1673
1674     case DF_REF_ORDER_BY_REG_WITH_NOTES:
1675       df_reorganize_refs_by_reg (&df->use_info, false, true, true);
1676       break;
1677
1678     case DF_REF_ORDER_BY_INSN:
1679       df_reorganize_refs_by_insn (&df->use_info, false, true, false);
1680       break;
1681
1682     case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1683       df_reorganize_refs_by_insn (&df->use_info, false, true, true);
1684       break;
1685
1686     case DF_REF_ORDER_NO_TABLE:
1687       free (df->use_info.refs);
1688       df->use_info.refs = NULL;
1689       df->use_info.refs_size = 0;
1690       break;
1691
1692     case DF_REF_ORDER_UNORDERED:
1693     case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1694       gcc_unreachable ();
1695       break;
1696     }
1697
1698   df->use_info.ref_order = order;
1699 }
1700
1701
1702 /* If the def refs in DF are not organized, reorganize them.  */
1703
1704 void
1705 df_maybe_reorganize_def_refs (enum df_ref_order order)
1706 {
1707   if (order == df->def_info.ref_order)
1708     return;
1709
1710   switch (order)
1711     {
1712     case DF_REF_ORDER_BY_REG:
1713       df_reorganize_refs_by_reg (&df->def_info, true, false, false);
1714       break;
1715
1716     case DF_REF_ORDER_BY_INSN:
1717       df_reorganize_refs_by_insn (&df->def_info, true, false, false);
1718       break;
1719
1720     case DF_REF_ORDER_NO_TABLE:
1721       free (df->def_info.refs);
1722       df->def_info.refs = NULL;
1723       df->def_info.refs_size = 0;
1724       break;
1725
1726     case DF_REF_ORDER_BY_INSN_WITH_NOTES:
1727     case DF_REF_ORDER_BY_REG_WITH_NOTES:
1728     case DF_REF_ORDER_UNORDERED:
1729     case DF_REF_ORDER_UNORDERED_WITH_NOTES:
1730       gcc_unreachable ();
1731       break;
1732     }
1733
1734   df->def_info.ref_order = order;
1735 }
1736
1737
1738 /* Change all of the basic block references in INSN to use the insn's
1739    current basic block.  This function is called from routines that move
1740    instructions from one block to another.  */
1741
1742 void
1743 df_insn_change_bb (rtx_insn *insn, basic_block new_bb)
1744 {
1745   basic_block old_bb = BLOCK_FOR_INSN (insn);
1746   struct df_insn_info *insn_info;
1747   unsigned int uid = INSN_UID (insn);
1748
1749   if (old_bb == new_bb)
1750     return;
1751
1752   set_block_for_insn (insn, new_bb);
1753
1754   if (!df)
1755     return;
1756
1757   if (dump_file)
1758     fprintf (dump_file, "changing bb of uid %d\n", uid);
1759
1760   insn_info = DF_INSN_UID_SAFE_GET (uid);
1761   if (insn_info == NULL)
1762     {
1763       if (dump_file)
1764         fprintf (dump_file, "  unscanned insn\n");
1765       df_insn_rescan (insn);
1766       return;
1767     }
1768
1769   if (!INSN_P (insn))
1770     return;
1771
1772   df_set_bb_dirty (new_bb);
1773   if (old_bb)
1774     {
1775       if (dump_file)
1776         fprintf (dump_file, "  from %d to %d\n",
1777                  old_bb->index, new_bb->index);
1778       df_set_bb_dirty (old_bb);
1779     }
1780   else
1781     if (dump_file)
1782       fprintf (dump_file, "  to %d\n", new_bb->index);
1783 }
1784
1785
1786 /* Helper function for df_ref_change_reg_with_loc.  */
1787
1788 static void
1789 df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
1790                               struct df_reg_info *new_df,
1791                               unsigned int new_regno, rtx loc)
1792 {
1793   df_ref the_ref = old_df->reg_chain;
1794
1795   while (the_ref)
1796     {
1797       if ((!DF_REF_IS_ARTIFICIAL (the_ref))
1798           && DF_REF_LOC (the_ref)
1799           && (*DF_REF_LOC (the_ref) == loc))
1800         {
1801           df_ref next_ref = DF_REF_NEXT_REG (the_ref);
1802           df_ref prev_ref = DF_REF_PREV_REG (the_ref);
1803           df_ref *ref_ptr;
1804           struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
1805
1806           DF_REF_REGNO (the_ref) = new_regno;
1807           DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
1808
1809           /* Pull the_ref out of the old regno chain.  */
1810           if (prev_ref)
1811             DF_REF_NEXT_REG (prev_ref) = next_ref;
1812           else
1813             old_df->reg_chain = next_ref;
1814           if (next_ref)
1815             DF_REF_PREV_REG (next_ref) = prev_ref;
1816           old_df->n_refs--;
1817
1818           /* Put the ref into the new regno chain.  */
1819           DF_REF_PREV_REG (the_ref) = NULL;
1820           DF_REF_NEXT_REG (the_ref) = new_df->reg_chain;
1821           if (new_df->reg_chain)
1822             DF_REF_PREV_REG (new_df->reg_chain) = the_ref;
1823           new_df->reg_chain = the_ref;
1824           new_df->n_refs++;
1825           if (DF_REF_BB (the_ref))
1826             df_set_bb_dirty (DF_REF_BB (the_ref));
1827
1828           /* Need to sort the record again that the ref was in because
1829              the regno is a sorting key.  First, find the right
1830              record.  */
1831           if (DF_REF_REG_DEF_P (the_ref))
1832             ref_ptr = &insn_info->defs;
1833           else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
1834             ref_ptr = &insn_info->eq_uses;
1835           else
1836             ref_ptr = &insn_info->uses;
1837           if (dump_file)
1838             fprintf (dump_file, "changing reg in insn %d\n",
1839                      DF_REF_INSN_UID (the_ref));
1840
1841           /* Stop if we find the current reference or where the reference
1842              needs to be.  */
1843           while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
1844             ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1845           if (*ref_ptr != the_ref)
1846             {
1847               /* The reference needs to be promoted up the list.  */
1848               df_ref next = DF_REF_NEXT_LOC (the_ref);
1849               DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1850               *ref_ptr = the_ref;
1851               do
1852                 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1853               while (*ref_ptr != the_ref);
1854               *ref_ptr = next;
1855             }
1856           else if (DF_REF_NEXT_LOC (the_ref)
1857                    && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
1858             {
1859               /* The reference needs to be demoted down the list.  */
1860               *ref_ptr = DF_REF_NEXT_LOC (the_ref);
1861               do
1862                 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
1863               while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
1864               DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
1865               *ref_ptr = the_ref;
1866             }
1867
1868           the_ref = next_ref;
1869         }
1870       else
1871         the_ref = DF_REF_NEXT_REG (the_ref);
1872     }
1873 }
1874
1875
1876 /* Change the regno of register LOC to NEW_REGNO and update the df
1877    information accordingly.  Refs that do not match LOC are not changed
1878    which means that artificial refs are not changed since they have no loc.
1879    This call is to support the SET_REGNO macro. */
1880
1881 void
1882 df_ref_change_reg_with_loc (rtx loc, unsigned int new_regno)
1883 {
1884   unsigned int old_regno = REGNO (loc);
1885   if (old_regno == new_regno)
1886     return;
1887
1888   if (df)
1889     {
1890       df_grow_reg_info ();
1891
1892       df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno),
1893                                     DF_REG_DEF_GET (new_regno),
1894                                     new_regno, loc);
1895       df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno),
1896                                     DF_REG_USE_GET (new_regno),
1897                                     new_regno, loc);
1898       df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno),
1899                                     DF_REG_EQ_USE_GET (new_regno),
1900                                     new_regno, loc);
1901     }
1902   set_mode_and_regno (loc, GET_MODE (loc), new_regno);
1903 }
1904
1905
1906 /* Delete the mw_hardregs that point into the eq_notes.  */
1907
1908 static void
1909 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
1910 {
1911   struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
1912   struct df_scan_problem_data *problem_data
1913     = (struct df_scan_problem_data *) df_scan->problem_data;
1914
1915   while (*mw_ptr)
1916     {
1917       df_mw_hardreg *mw = *mw_ptr;
1918       if (mw->flags & DF_REF_IN_NOTE)
1919         {
1920           *mw_ptr = DF_MWS_NEXT (mw);
1921           problem_data->mw_reg_pool->remove (mw);
1922         }
1923       else
1924         mw_ptr = &DF_MWS_NEXT (mw);
1925     }
1926 }
1927
1928
1929 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN.  */
1930
1931 void
1932 df_notes_rescan (rtx_insn *insn)
1933 {
1934   struct df_insn_info *insn_info;
1935   unsigned int uid = INSN_UID (insn);
1936
1937   if (!df)
1938     return;
1939
1940   /* The client has disabled rescanning and plans to do it itself.  */
1941   if (df->changeable_flags & DF_NO_INSN_RESCAN)
1942     return;
1943
1944   /* Do nothing if the insn hasn't been emitted yet.  */
1945   if (!BLOCK_FOR_INSN (insn))
1946     return;
1947
1948   df_grow_bb_info (df_scan);
1949   df_grow_reg_info ();
1950
1951   insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn));
1952
1953   /* The client has deferred rescanning.  */
1954   if (df->changeable_flags & DF_DEFER_INSN_RESCAN)
1955     {
1956       if (!insn_info)
1957         {
1958           insn_info = df_insn_create_insn_record (insn);
1959           insn_info->defs = 0;
1960           insn_info->uses = 0;
1961           insn_info->eq_uses = 0;
1962           insn_info->mw_hardregs = 0;
1963         }
1964
1965       bitmap_clear_bit (&df->insns_to_delete, uid);
1966       /* If the insn is set to be rescanned, it does not need to also
1967          be notes rescanned.  */
1968       if (!bitmap_bit_p (&df->insns_to_rescan, uid))
1969         bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn));
1970       return;
1971     }
1972
1973   bitmap_clear_bit (&df->insns_to_delete, uid);
1974   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
1975
1976   if (insn_info)
1977     {
1978       basic_block bb = BLOCK_FOR_INSN (insn);
1979       rtx note;
1980       struct df_collection_rec collection_rec;
1981       unsigned int i;
1982
1983       df_mw_hardreg_chain_delete_eq_uses (insn_info);
1984       df_ref_chain_delete (insn_info->eq_uses);
1985       insn_info->eq_uses = NULL;
1986
1987       /* Process REG_EQUIV/REG_EQUAL notes */
1988       for (note = REG_NOTES (insn); note;
1989            note = XEXP (note, 1))
1990         {
1991           switch (REG_NOTE_KIND (note))
1992             {
1993             case REG_EQUIV:
1994             case REG_EQUAL:
1995               df_uses_record (&collection_rec,
1996                               &XEXP (note, 0), DF_REF_REG_USE,
1997                               bb, insn_info, DF_REF_IN_NOTE);
1998             default:
1999               break;
2000             }
2001         }
2002
2003       /* Find some place to put any new mw_hardregs.  */
2004       df_canonize_collection_rec (&collection_rec);
2005       struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
2006       FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
2007         {
2008           while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
2009             mw_ptr = &DF_MWS_NEXT (*mw_ptr);
2010           DF_MWS_NEXT (mw) = *mw_ptr;
2011           *mw_ptr = mw;
2012           mw_ptr = &DF_MWS_NEXT (mw);
2013         }
2014       df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
2015     }
2016   else
2017     df_insn_rescan (insn);
2018
2019 }
2020
2021 \f
2022 /*----------------------------------------------------------------------------
2023    Hard core instruction scanning code.  No external interfaces here,
2024    just a lot of routines that look inside insns.
2025 ----------------------------------------------------------------------------*/
2026
2027
2028 /* Return true if the contents of two df_ref's are identical.
2029    It ignores DF_REF_MARKER.  */
2030
2031 static bool
2032 df_ref_equal_p (df_ref ref1, df_ref ref2)
2033 {
2034   if (!ref2)
2035     return false;
2036
2037   if (ref1 == ref2)
2038     return true;
2039
2040   if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)
2041       || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)
2042       || DF_REF_REG (ref1) != DF_REF_REG (ref2)
2043       || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)
2044       || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))
2045           != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)))
2046       || DF_REF_BB (ref1) != DF_REF_BB (ref2)
2047       || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2))
2048     return false;
2049
2050   switch (DF_REF_CLASS (ref1))
2051     {
2052     case DF_REF_ARTIFICIAL:
2053     case DF_REF_BASE:
2054       return true;
2055
2056     case DF_REF_REGULAR:
2057       return DF_REF_LOC (ref1) == DF_REF_LOC (ref2);
2058
2059     default:
2060       gcc_unreachable ();
2061     }
2062   return false;
2063 }
2064
2065
2066 /* Compare REF1 and REF2 for sorting.  This is only called from places
2067    where all of the refs are of the same type, in the same insn, and
2068    have the same bb.  So these fields are not checked.  */
2069
2070 static int
2071 df_ref_compare (df_ref ref1, df_ref ref2)
2072 {
2073   if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
2074     return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
2075
2076   if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2))
2077     return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2);
2078
2079   if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2))
2080     return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2);
2081
2082   if (DF_REF_REG (ref1) != DF_REF_REG (ref2))
2083     return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2084
2085   /* Cannot look at the LOC field on artificial refs.  */
2086   if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL
2087       && DF_REF_LOC (ref1) != DF_REF_LOC (ref2))
2088     return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2089
2090   if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2))
2091     {
2092       /* If two refs are identical except that one of them has is from
2093          a mw and one is not, we need to have the one with the mw
2094          first.  */
2095       if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) ==
2096           DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG))
2097         return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2);
2098       else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG))
2099         return -1;
2100       else
2101         return 1;
2102     }
2103
2104   return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
2105 }
2106
2107 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2.  */
2108
2109 static int
2110 df_ref_ptr_compare (const void *r1, const void *r2)
2111 {
2112   return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
2113 }
2114
2115 /* Sort and compress a set of refs.  */
2116
2117 static void
2118 df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
2119 {
2120   unsigned int count;
2121   unsigned int i;
2122   unsigned int dist = 0;
2123
2124   count = ref_vec->length ();
2125
2126   /* If there are 1 or 0 elements, there is nothing to do.  */
2127   if (count < 2)
2128     return;
2129   else if (count == 2)
2130     {
2131       df_ref r0 = (*ref_vec)[0];
2132       df_ref r1 = (*ref_vec)[1];
2133       if (df_ref_compare (r0, r1) > 0)
2134         std::swap ((*ref_vec)[0], (*ref_vec)[1]);
2135     }
2136   else
2137     {
2138       for (i = 0; i < count - 1; i++)
2139         {
2140           df_ref r0 = (*ref_vec)[i];
2141           df_ref r1 = (*ref_vec)[i + 1];
2142           if (df_ref_compare (r0, r1) >= 0)
2143             break;
2144         }
2145       /* If the array is already strictly ordered,
2146          which is the most common case for large COUNT case
2147          (which happens for CALL INSNs),
2148          no need to sort and filter out duplicate.
2149          Simply return the count.
2150          Make sure DF_GET_ADD_REFS adds refs in the increasing order
2151          of DF_REF_COMPARE.  */
2152       if (i == count - 1)
2153         return;
2154       ref_vec->qsort (df_ref_ptr_compare);
2155     }
2156
2157   for (i=0; i<count-dist; i++)
2158     {
2159       /* Find the next ref that is not equal to the current ref.  */
2160       while (i + dist + 1 < count
2161              && df_ref_equal_p ((*ref_vec)[i],
2162                                 (*ref_vec)[i + dist + 1]))
2163         {
2164           df_free_ref ((*ref_vec)[i + dist + 1]);
2165           dist++;
2166         }
2167       /* Copy it down to the next position.  */
2168       if (dist && i + dist + 1 < count)
2169         (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1];
2170     }
2171
2172   count -= dist;
2173   ref_vec->truncate (count);
2174 }
2175
2176
2177 /* Return true if the contents of two df_ref's are identical.
2178    It ignores DF_REF_MARKER.  */
2179
2180 static bool
2181 df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
2182 {
2183   if (!mw2)
2184     return false;
2185   return (mw1 == mw2) ||
2186     (mw1->mw_reg == mw2->mw_reg
2187      && mw1->type == mw2->type
2188      && mw1->flags == mw2->flags
2189      && mw1->start_regno == mw2->start_regno
2190      && mw1->end_regno == mw2->end_regno);
2191 }
2192
2193
2194 /* Compare MW1 and MW2 for sorting.  */
2195
2196 static int
2197 df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
2198 {
2199   if (mw1->type != mw2->type)
2200     return mw1->type - mw2->type;
2201
2202   if (mw1->flags != mw2->flags)
2203     return mw1->flags - mw2->flags;
2204
2205   if (mw1->start_regno != mw2->start_regno)
2206     return mw1->start_regno - mw2->start_regno;
2207
2208   if (mw1->end_regno != mw2->end_regno)
2209     return mw1->end_regno - mw2->end_regno;
2210
2211   if (mw1->mw_reg != mw2->mw_reg)
2212     return mw1->mw_order - mw2->mw_order;
2213
2214   return 0;
2215 }
2216
2217 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2.  */
2218
2219 static int
2220 df_mw_ptr_compare (const void *m1, const void *m2)
2221 {
2222   return df_mw_compare (*(const df_mw_hardreg *const *) m1,
2223                         *(const df_mw_hardreg *const *) m2);
2224 }
2225
2226 /* Sort and compress a set of refs.  */
2227
2228 static void
2229 df_sort_and_compress_mws (vec<df_mw_hardreg *, va_heap> *mw_vec)
2230 {
2231   unsigned int count;
2232   struct df_scan_problem_data *problem_data
2233     = (struct df_scan_problem_data *) df_scan->problem_data;
2234   unsigned int i;
2235   unsigned int dist = 0;
2236
2237   count = mw_vec->length ();
2238   if (count < 2)
2239     return;
2240   else if (count == 2)
2241     {
2242       struct df_mw_hardreg *m0 = (*mw_vec)[0];
2243       struct df_mw_hardreg *m1 = (*mw_vec)[1];
2244       if (df_mw_compare (m0, m1) > 0)
2245         {
2246           struct df_mw_hardreg *tmp = (*mw_vec)[0];
2247           (*mw_vec)[0] = (*mw_vec)[1];
2248           (*mw_vec)[1] = tmp;
2249         }
2250     }
2251   else
2252     mw_vec->qsort (df_mw_ptr_compare);
2253
2254   for (i=0; i<count-dist; i++)
2255     {
2256       /* Find the next ref that is not equal to the current ref.  */
2257       while (i + dist + 1 < count
2258              && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1]))
2259         {
2260           problem_data->mw_reg_pool->remove ((*mw_vec)[i + dist + 1]);
2261           dist++;
2262         }
2263       /* Copy it down to the next position.  */
2264       if (dist && i + dist + 1 < count)
2265         (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1];
2266     }
2267
2268   count -= dist;
2269   mw_vec->truncate (count);
2270 }
2271
2272
2273 /* Sort and remove duplicates from the COLLECTION_REC.  */
2274
2275 static void
2276 df_canonize_collection_rec (struct df_collection_rec *collection_rec)
2277 {
2278   df_sort_and_compress_refs (&collection_rec->def_vec);
2279   df_sort_and_compress_refs (&collection_rec->use_vec);
2280   df_sort_and_compress_refs (&collection_rec->eq_use_vec);
2281   df_sort_and_compress_mws (&collection_rec->mw_vec);
2282 }
2283
2284
2285 /* Add the new df_ref to appropriate reg_info/ref_info chains.  */
2286
2287 static void
2288 df_install_ref (df_ref this_ref,
2289                 struct df_reg_info *reg_info,
2290                 struct df_ref_info *ref_info,
2291                 bool add_to_table)
2292 {
2293   unsigned int regno = DF_REF_REGNO (this_ref);
2294   /* Add the ref to the reg_{def,use,eq_use} chain.  */
2295   df_ref head = reg_info->reg_chain;
2296
2297   reg_info->reg_chain = this_ref;
2298   reg_info->n_refs++;
2299
2300   if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE))
2301     {
2302       gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2303       df->hard_regs_live_count[regno]++;
2304     }
2305
2306   gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL
2307                        && DF_REF_PREV_REG (this_ref) == NULL);
2308
2309   DF_REF_NEXT_REG (this_ref) = head;
2310
2311   /* We cannot actually link to the head of the chain.  */
2312   DF_REF_PREV_REG (this_ref) = NULL;
2313
2314   if (head)
2315     DF_REF_PREV_REG (head) = this_ref;
2316
2317   if (add_to_table)
2318     {
2319       gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE);
2320       df_check_and_grow_ref_info (ref_info, 1);
2321       DF_REF_ID (this_ref) = ref_info->table_size;
2322       /* Add the ref to the big array of defs.  */
2323       ref_info->refs[ref_info->table_size] = this_ref;
2324       ref_info->table_size++;
2325     }
2326   else
2327     DF_REF_ID (this_ref) = -1;
2328
2329   ref_info->total_size++;
2330 }
2331
2332
2333 /* This function takes one of the groups of refs (defs, uses or
2334    eq_uses) and installs the entire group into the insn.  It also adds
2335    each of these refs into the appropriate chains.  */
2336
2337 static df_ref
2338 df_install_refs (basic_block bb,
2339                  const vec<df_ref, va_heap> *old_vec,
2340                  struct df_reg_info **reg_info,
2341                  struct df_ref_info *ref_info,
2342                  bool is_notes)
2343 {
2344   unsigned int count = old_vec->length ();
2345   if (count)
2346     {
2347       bool add_to_table;
2348       df_ref this_ref;
2349       unsigned int ix;
2350
2351       switch (ref_info->ref_order)
2352         {
2353         case DF_REF_ORDER_UNORDERED_WITH_NOTES:
2354         case DF_REF_ORDER_BY_REG_WITH_NOTES:
2355         case DF_REF_ORDER_BY_INSN_WITH_NOTES:
2356           ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES;
2357           add_to_table = true;
2358           break;
2359         case DF_REF_ORDER_UNORDERED:
2360         case DF_REF_ORDER_BY_REG:
2361         case DF_REF_ORDER_BY_INSN:
2362           ref_info->ref_order = DF_REF_ORDER_UNORDERED;
2363           add_to_table = !is_notes;
2364           break;
2365         default:
2366           add_to_table = false;
2367           break;
2368         }
2369
2370       /* Do not add if ref is not in the right blocks.  */
2371       if (add_to_table && df->analyze_subset)
2372         add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index);
2373
2374       FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
2375         {
2376           DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
2377                                         ? (*old_vec)[ix + 1]
2378                                         : NULL);
2379           df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
2380                           ref_info, add_to_table);
2381         }
2382       return (*old_vec)[0];
2383     }
2384   else
2385     return 0;
2386 }
2387
2388
2389 /* This function takes the mws installs the entire group into the
2390    insn.  */
2391
2392 static struct df_mw_hardreg *
2393 df_install_mws (const vec<df_mw_hardreg *, va_heap> *old_vec)
2394 {
2395   unsigned int count = old_vec->length ();
2396   if (count)
2397     {
2398       for (unsigned int i = 0; i < count - 1; i++)
2399         DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
2400       DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
2401       return (*old_vec)[0];
2402     }
2403   else
2404     return 0;
2405 }
2406
2407
2408 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2409    chains and update other necessary information.  */
2410
2411 static void
2412 df_refs_add_to_chains (struct df_collection_rec *collection_rec,
2413                        basic_block bb, rtx_insn *insn, unsigned int flags)
2414 {
2415   if (insn)
2416     {
2417       struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn);
2418       /* If there is a vector in the collection rec, add it to the
2419          insn.  A null rec is a signal that the caller will handle the
2420          chain specially.  */
2421       if (flags & copy_defs)
2422         {
2423           gcc_checking_assert (!insn_rec->defs);
2424           insn_rec->defs
2425             = df_install_refs (bb, &collection_rec->def_vec,
2426                                df->def_regs,
2427                                &df->def_info, false);
2428         }
2429       if (flags & copy_uses)
2430         {
2431           gcc_checking_assert (!insn_rec->uses);
2432           insn_rec->uses
2433             = df_install_refs (bb, &collection_rec->use_vec,
2434                                df->use_regs,
2435                                &df->use_info, false);
2436         }
2437       if (flags & copy_eq_uses)
2438         {
2439           gcc_checking_assert (!insn_rec->eq_uses);
2440           insn_rec->eq_uses
2441             = df_install_refs (bb, &collection_rec->eq_use_vec,
2442                                df->eq_use_regs,
2443                                &df->use_info, true);
2444         }
2445       if (flags & copy_mw)
2446         {
2447           gcc_checking_assert (!insn_rec->mw_hardregs);
2448           insn_rec->mw_hardregs
2449             = df_install_mws (&collection_rec->mw_vec);
2450         }
2451     }
2452   else
2453     {
2454       struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
2455
2456       gcc_checking_assert (!bb_info->artificial_defs);
2457       bb_info->artificial_defs
2458         = df_install_refs (bb, &collection_rec->def_vec,
2459                            df->def_regs,
2460                            &df->def_info, false);
2461       gcc_checking_assert (!bb_info->artificial_uses);
2462       bb_info->artificial_uses
2463         = df_install_refs (bb, &collection_rec->use_vec,
2464                            df->use_regs,
2465                            &df->use_info, false);
2466     }
2467 }
2468
2469
2470 /* Allocate a ref and initialize its fields.  */
2471
2472 static df_ref
2473 df_ref_create_structure (enum df_ref_class cl,
2474                          struct df_collection_rec *collection_rec,
2475                          rtx reg, rtx *loc,
2476                          basic_block bb, struct df_insn_info *info,
2477                          enum df_ref_type ref_type,
2478                          int ref_flags)
2479 {
2480   df_ref this_ref = NULL;
2481   unsigned int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2482   struct df_scan_problem_data *problem_data
2483     = (struct df_scan_problem_data *) df_scan->problem_data;
2484
2485   switch (cl)
2486     {
2487     case DF_REF_BASE:
2488       this_ref = (df_ref) (problem_data->ref_base_pool->allocate ());
2489       gcc_checking_assert (loc == NULL);
2490       break;
2491
2492     case DF_REF_ARTIFICIAL:
2493       this_ref = (df_ref) (problem_data->ref_artificial_pool->allocate ());
2494       this_ref->artificial_ref.bb = bb;
2495       gcc_checking_assert (loc == NULL);
2496       break;
2497
2498     case DF_REF_REGULAR:
2499       this_ref = (df_ref) (problem_data->ref_regular_pool->allocate ());
2500       this_ref->regular_ref.loc = loc;
2501       gcc_checking_assert (loc);
2502       break;
2503     }
2504
2505   DF_REF_CLASS (this_ref) = cl;
2506   DF_REF_ID (this_ref) = -1;
2507   DF_REF_REG (this_ref) = reg;
2508   DF_REF_REGNO (this_ref) =  regno;
2509   DF_REF_TYPE (this_ref) = ref_type;
2510   DF_REF_INSN_INFO (this_ref) = info;
2511   DF_REF_CHAIN (this_ref) = NULL;
2512   DF_REF_FLAGS (this_ref) = ref_flags;
2513   DF_REF_NEXT_REG (this_ref) = NULL;
2514   DF_REF_PREV_REG (this_ref) = NULL;
2515   DF_REF_ORDER (this_ref) = df->ref_order++;
2516
2517   /* We need to clear this bit because fwprop, and in the future
2518      possibly other optimizations sometimes create new refs using ond
2519      refs as the model.  */
2520   DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE);
2521
2522   /* See if this ref needs to have DF_HARD_REG_LIVE bit set.  */
2523   if (regno < FIRST_PSEUDO_REGISTER
2524       && !DF_REF_IS_ARTIFICIAL (this_ref)
2525       && !DEBUG_INSN_P (DF_REF_INSN (this_ref)))
2526     {
2527       if (DF_REF_REG_DEF_P (this_ref))
2528         {
2529           if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
2530             DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2531         }
2532       else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
2533                  && (regno == FRAME_POINTER_REGNUM
2534                      || regno == ARG_POINTER_REGNUM)))
2535         DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE);
2536     }
2537
2538   if (collection_rec)
2539     {
2540       if (DF_REF_REG_DEF_P (this_ref))
2541         collection_rec->def_vec.safe_push (this_ref);
2542       else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE)
2543         collection_rec->eq_use_vec.safe_push (this_ref);
2544       else
2545         collection_rec->use_vec.safe_push (this_ref);
2546     }
2547   else
2548     df_install_ref_incremental (this_ref);
2549
2550   return this_ref;
2551 }
2552
2553
2554 /* Create new references of type DF_REF_TYPE for each part of register REG
2555    at address LOC within INSN of BB.  */
2556
2557
2558 static void
2559 df_ref_record (enum df_ref_class cl,
2560                struct df_collection_rec *collection_rec,
2561                rtx reg, rtx *loc,
2562                basic_block bb, struct df_insn_info *insn_info,
2563                enum df_ref_type ref_type,
2564                int ref_flags)
2565 {
2566   unsigned int regno;
2567
2568   gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
2569
2570   regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
2571   if (regno < FIRST_PSEUDO_REGISTER)
2572     {
2573       struct df_mw_hardreg *hardreg = NULL;
2574       struct df_scan_problem_data *problem_data
2575         = (struct df_scan_problem_data *) df_scan->problem_data;
2576       unsigned int i;
2577       unsigned int endregno;
2578       df_ref ref;
2579
2580       if (GET_CODE (reg) == SUBREG)
2581         {
2582           regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
2583                                         SUBREG_BYTE (reg), GET_MODE (reg));
2584           endregno = regno + subreg_nregs (reg);
2585         }
2586       else
2587         endregno = END_REGNO (reg);
2588
2589       /*  If this is a multiword hardreg, we create some extra
2590           datastructures that will enable us to easily build REG_DEAD
2591           and REG_UNUSED notes.  */
2592       if (collection_rec
2593           && (endregno != regno + 1) && insn_info)
2594         {
2595           /* Sets to a subreg of a multiword register are partial.
2596              Sets to a non-subreg of a multiword register are not.  */
2597           if (GET_CODE (reg) == SUBREG)
2598             ref_flags |= DF_REF_PARTIAL;
2599           ref_flags |= DF_REF_MW_HARDREG;
2600
2601           hardreg = problem_data->mw_reg_pool->allocate ();
2602           hardreg->type = ref_type;
2603           hardreg->flags = ref_flags;
2604           hardreg->mw_reg = reg;
2605           hardreg->start_regno = regno;
2606           hardreg->end_regno = endregno - 1;
2607           hardreg->mw_order = df->ref_order++;
2608           collection_rec->mw_vec.safe_push (hardreg);
2609         }
2610
2611       for (i = regno; i < endregno; i++)
2612         {
2613           ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc,
2614                                          bb, insn_info, ref_type, ref_flags);
2615
2616           gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i);
2617         }
2618     }
2619   else
2620     {
2621       df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info,
2622                                ref_type, ref_flags);
2623     }
2624 }
2625
2626
2627 /* Process all the registers defined in the rtx pointed by LOC.
2628    Autoincrement/decrement definitions will be picked up by df_uses_record.
2629    Any change here has to be matched in df_find_hard_reg_defs_1.  */
2630
2631 static void
2632 df_def_record_1 (struct df_collection_rec *collection_rec,
2633                  rtx *loc, basic_block bb, struct df_insn_info *insn_info,
2634                  int flags)
2635 {
2636   rtx dst = *loc;
2637
2638   /* It is legal to have a set destination be a parallel. */
2639   if (GET_CODE (dst) == PARALLEL)
2640     {
2641       int i;
2642       for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2643         {
2644           rtx temp = XVECEXP (dst, 0, i);
2645           gcc_assert (GET_CODE (temp) == EXPR_LIST);
2646           df_def_record_1 (collection_rec, &XEXP (temp, 0),
2647                            bb, insn_info, flags);
2648         }
2649       return;
2650     }
2651
2652   if (GET_CODE (dst) == STRICT_LOW_PART)
2653     {
2654       flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART;
2655
2656       loc = &XEXP (dst, 0);
2657       dst = *loc;
2658     }
2659
2660   if (GET_CODE (dst) == ZERO_EXTRACT)
2661     {
2662       flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT;
2663
2664       loc = &XEXP (dst, 0);
2665       dst = *loc;
2666     }
2667
2668   /* At this point if we do not have a reg or a subreg, just return.  */
2669   if (REG_P (dst))
2670     {
2671       df_ref_record (DF_REF_REGULAR, collection_rec,
2672                      dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2673
2674       /* We want to keep sp alive everywhere - by making all
2675          writes to sp also use of sp. */
2676       if (REGNO (dst) == STACK_POINTER_REGNUM)
2677         df_ref_record (DF_REF_BASE, collection_rec,
2678                        dst, NULL, bb, insn_info, DF_REF_REG_USE, flags);
2679     }
2680   else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst)))
2681     {
2682       if (read_modify_subreg_p (dst))
2683         flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL;
2684
2685       flags |= DF_REF_SUBREG;
2686
2687       df_ref_record (DF_REF_REGULAR, collection_rec,
2688                      dst, loc, bb, insn_info, DF_REF_REG_DEF, flags);
2689     }
2690 }
2691
2692
2693 /* Process all the registers defined in the pattern rtx, X.  Any change
2694    here has to be matched in df_find_hard_reg_defs.  */
2695
2696 static void
2697 df_defs_record (struct df_collection_rec *collection_rec,
2698                 rtx x, basic_block bb, struct df_insn_info *insn_info,
2699                 int flags)
2700 {
2701   RTX_CODE code = GET_CODE (x);
2702   int i;
2703
2704   switch (code)
2705     {
2706     case SET:
2707       df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags);
2708       break;
2709
2710     case CLOBBER:
2711       flags |= DF_REF_MUST_CLOBBER;
2712       df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags);
2713       break;
2714
2715     case COND_EXEC:
2716       df_defs_record (collection_rec, COND_EXEC_CODE (x),
2717                       bb, insn_info, DF_REF_CONDITIONAL);
2718       break;
2719
2720     case PARALLEL:
2721       for (i = 0; i < XVECLEN (x, 0); i++)
2722         df_defs_record (collection_rec, XVECEXP (x, 0, i),
2723                         bb, insn_info, flags);
2724       break;
2725     default:
2726       /* No DEFs to record in other cases */
2727       break;
2728     }
2729 }
2730
2731 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2732    destination of a set or clobber.  This has to match the logic in
2733    df_defs_record_1.  */
2734
2735 static void
2736 df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs)
2737 {
2738   /* It is legal to have a set destination be a parallel. */
2739   if (GET_CODE (dst) == PARALLEL)
2740     {
2741       int i;
2742       for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
2743         {
2744           rtx temp = XVECEXP (dst, 0, i);
2745           gcc_assert (GET_CODE (temp) == EXPR_LIST);
2746           df_find_hard_reg_defs_1 (XEXP (temp, 0), defs);
2747         }
2748       return;
2749     }
2750
2751   if (GET_CODE (dst) == STRICT_LOW_PART)
2752       dst = XEXP (dst, 0);
2753
2754   if (GET_CODE (dst) == ZERO_EXTRACT)
2755       dst = XEXP (dst, 0);
2756
2757   /* At this point if we do not have a reg or a subreg, just return.  */
2758   if (REG_P (dst) && HARD_REGISTER_P (dst))
2759     SET_HARD_REG_BIT (*defs, REGNO (dst));
2760   else if (GET_CODE (dst) == SUBREG
2761            && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst))
2762     SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst)));
2763 }
2764
2765 /* Set bits in *DEFS for hard registers defined in the pattern X.  This
2766    has to match the logic in df_defs_record.  */
2767
2768 static void
2769 df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs)
2770 {
2771   RTX_CODE code = GET_CODE (x);
2772   int i;
2773
2774   switch (code)
2775     {
2776     case SET:
2777       df_find_hard_reg_defs_1 (SET_DEST (x), defs);
2778       break;
2779
2780     case CLOBBER:
2781       df_find_hard_reg_defs_1 (XEXP (x, 0), defs);
2782       break;
2783
2784     case COND_EXEC:
2785       df_find_hard_reg_defs (COND_EXEC_CODE (x), defs);
2786       break;
2787
2788     case PARALLEL:
2789       for (i = 0; i < XVECLEN (x, 0); i++)
2790         df_find_hard_reg_defs (XVECEXP (x, 0, i), defs);
2791       break;
2792     default:
2793       /* No DEFs to record in other cases */
2794       break;
2795     }
2796 }
2797
2798
2799 /* Process all the registers used in the rtx at address LOC.  */
2800
2801 static void
2802 df_uses_record (struct df_collection_rec *collection_rec,
2803                 rtx *loc, enum df_ref_type ref_type,
2804                 basic_block bb, struct df_insn_info *insn_info,
2805                 int flags)
2806 {
2807   RTX_CODE code;
2808   rtx x;
2809
2810  retry:
2811   x = *loc;
2812   if (!x)
2813     return;
2814   code = GET_CODE (x);
2815   switch (code)
2816     {
2817     case LABEL_REF:
2818     case SYMBOL_REF:
2819     case CONST:
2820     CASE_CONST_ANY:
2821     case PC:
2822     case CC0:
2823     case ADDR_VEC:
2824     case ADDR_DIFF_VEC:
2825       return;
2826
2827     case CLOBBER:
2828       /* If we are clobbering a MEM, mark any registers inside the address
2829          as being used.  */
2830       if (MEM_P (XEXP (x, 0)))
2831         df_uses_record (collection_rec,
2832                         &XEXP (XEXP (x, 0), 0),
2833                         DF_REF_REG_MEM_STORE,
2834                         bb, insn_info,
2835                         flags);
2836
2837       /* If we're clobbering a REG then we have a def so ignore.  */
2838       return;
2839
2840     case MEM:
2841       df_uses_record (collection_rec,
2842                       &XEXP (x, 0), DF_REF_REG_MEM_LOAD,
2843                       bb, insn_info, flags & DF_REF_IN_NOTE);
2844       return;
2845
2846     case SUBREG:
2847       /* While we're here, optimize this case.  */
2848       flags |= DF_REF_PARTIAL;
2849       /* In case the SUBREG is not of a REG, do not optimize.  */
2850       if (!REG_P (SUBREG_REG (x)))
2851         {
2852           loc = &SUBREG_REG (x);
2853           df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags);
2854           return;
2855         }
2856       /* Fall through */
2857
2858     case REG:
2859       df_ref_record (DF_REF_REGULAR, collection_rec,
2860                      x, loc, bb, insn_info,
2861                      ref_type, flags);
2862       return;
2863
2864     case SIGN_EXTRACT:
2865     case ZERO_EXTRACT:
2866       {
2867         df_uses_record (collection_rec,
2868                         &XEXP (x, 1), ref_type, bb, insn_info, flags);
2869         df_uses_record (collection_rec,
2870                         &XEXP (x, 2), ref_type, bb, insn_info, flags);
2871
2872         /* If the parameters to the zero or sign extract are
2873            constants, strip them off and recurse, otherwise there is
2874            no information that we can gain from this operation.  */
2875         if (code == ZERO_EXTRACT)
2876           flags |= DF_REF_ZERO_EXTRACT;
2877         else
2878           flags |= DF_REF_SIGN_EXTRACT;
2879
2880         df_uses_record (collection_rec,
2881                         &XEXP (x, 0), ref_type, bb, insn_info, flags);
2882         return;
2883       }
2884       break;
2885
2886     case SET:
2887       {
2888         rtx dst = SET_DEST (x);
2889         gcc_assert (!(flags & DF_REF_IN_NOTE));
2890         df_uses_record (collection_rec,
2891                         &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags);
2892
2893         switch (GET_CODE (dst))
2894           {
2895             case SUBREG:
2896               if (read_modify_subreg_p (dst))
2897                 {
2898                   df_uses_record (collection_rec, &SUBREG_REG (dst),
2899                                   DF_REF_REG_USE, bb, insn_info,
2900                                   flags | DF_REF_READ_WRITE | DF_REF_SUBREG);
2901                   break;
2902                 }
2903               /* Fall through.  */
2904             case REG:
2905             case PARALLEL:
2906             case SCRATCH:
2907             case PC:
2908             case CC0:
2909                 break;
2910             case MEM:
2911               df_uses_record (collection_rec, &XEXP (dst, 0),
2912                               DF_REF_REG_MEM_STORE, bb, insn_info, flags);
2913               break;
2914             case STRICT_LOW_PART:
2915               {
2916                 rtx *temp = &XEXP (dst, 0);
2917                 /* A strict_low_part uses the whole REG and not just the
2918                  SUBREG.  */
2919                 dst = XEXP (dst, 0);
2920                 df_uses_record (collection_rec,
2921                                 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp,
2922                                 DF_REF_REG_USE, bb, insn_info,
2923                                 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART);
2924               }
2925               break;
2926             case ZERO_EXTRACT:
2927               {
2928                 df_uses_record (collection_rec, &XEXP (dst, 1),
2929                                 DF_REF_REG_USE, bb, insn_info, flags);
2930                 df_uses_record (collection_rec, &XEXP (dst, 2),
2931                                 DF_REF_REG_USE, bb, insn_info, flags);
2932                 if (GET_CODE (XEXP (dst,0)) == MEM)
2933                   df_uses_record (collection_rec, &XEXP (dst, 0),
2934                                   DF_REF_REG_USE, bb, insn_info,
2935                                   flags);
2936                 else
2937                   df_uses_record (collection_rec, &XEXP (dst, 0),
2938                                   DF_REF_REG_USE, bb, insn_info,
2939                                   DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT);
2940               }
2941               break;
2942
2943             default:
2944               gcc_unreachable ();
2945           }
2946         return;
2947       }
2948
2949     case RETURN:
2950     case SIMPLE_RETURN:
2951       break;
2952
2953     case ASM_OPERANDS:
2954     case UNSPEC_VOLATILE:
2955     case TRAP_IF:
2956     case ASM_INPUT:
2957       {
2958         /* Traditional and volatile asm instructions must be
2959            considered to use and clobber all hard registers, all
2960            pseudo-registers and all of memory.  So must TRAP_IF and
2961            UNSPEC_VOLATILE operations.
2962
2963            Consider for instance a volatile asm that changes the fpu
2964            rounding mode.  An insn should not be moved across this
2965            even if it only uses pseudo-regs because it might give an
2966            incorrectly rounded result.
2967
2968            However, flow.c's liveness computation did *not* do this,
2969            giving the reasoning as " ?!? Unfortunately, marking all
2970            hard registers as live causes massive problems for the
2971            register allocator and marking all pseudos as live creates
2972            mountains of uninitialized variable warnings."
2973
2974            In order to maintain the status quo with regard to liveness
2975            and uses, we do what flow.c did and just mark any regs we
2976            can find in ASM_OPERANDS as used.  In global asm insns are
2977            scanned and regs_asm_clobbered is filled out.
2978
2979            For all ASM_OPERANDS, we must traverse the vector of input
2980            operands.  We can not just fall through here since then we
2981            would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
2982            which do not indicate traditional asms unlike their normal
2983            usage.  */
2984         if (code == ASM_OPERANDS)
2985           {
2986             int j;
2987
2988             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2989               df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j),
2990                               DF_REF_REG_USE, bb, insn_info, flags);
2991             return;
2992           }
2993         break;
2994       }
2995
2996     case VAR_LOCATION:
2997       df_uses_record (collection_rec,
2998                       &PAT_VAR_LOCATION_LOC (x),
2999                       DF_REF_REG_USE, bb, insn_info, flags);
3000       return;
3001
3002     case PRE_DEC:
3003     case POST_DEC:
3004     case PRE_INC:
3005     case POST_INC:
3006     case PRE_MODIFY:
3007     case POST_MODIFY:
3008       gcc_assert (!DEBUG_INSN_P (insn_info->insn));
3009       /* Catch the def of the register being modified.  */
3010       df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0),
3011                      bb, insn_info,
3012                      DF_REF_REG_DEF,
3013                      flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY);
3014
3015       /* ... Fall through to handle uses ...  */
3016
3017     default:
3018       break;
3019     }
3020
3021   /* Recursively scan the operands of this expression.  */
3022   {
3023     const char *fmt = GET_RTX_FORMAT (code);
3024     int i;
3025
3026     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3027       {
3028         if (fmt[i] == 'e')
3029           {
3030             /* Tail recursive case: save a function call level.  */
3031             if (i == 0)
3032               {
3033                 loc = &XEXP (x, 0);
3034                 goto retry;
3035               }
3036             df_uses_record (collection_rec, &XEXP (x, i), ref_type,
3037                             bb, insn_info, flags);
3038           }
3039         else if (fmt[i] == 'E')
3040           {
3041             int j;
3042             for (j = 0; j < XVECLEN (x, i); j++)
3043               df_uses_record (collection_rec,
3044                               &XVECEXP (x, i, j), ref_type,
3045                               bb, insn_info, flags);
3046           }
3047       }
3048   }
3049
3050   return;
3051 }
3052
3053
3054 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses.  */
3055
3056 static void
3057 df_get_conditional_uses (struct df_collection_rec *collection_rec)
3058 {
3059   unsigned int ix;
3060   df_ref ref;
3061
3062   FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref)
3063     {
3064       if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL))
3065         {
3066           df_ref use;
3067
3068           use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref),
3069                                          DF_REF_LOC (ref), DF_REF_BB (ref),
3070                                          DF_REF_INSN_INFO (ref), DF_REF_REG_USE,
3071                                          DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL);
3072           DF_REF_REGNO (use) = DF_REF_REGNO (ref);
3073         }
3074     }
3075 }
3076
3077
3078 /* Get call's extra defs and uses (track caller-saved registers). */
3079
3080 static void
3081 df_get_call_refs (struct df_collection_rec *collection_rec,
3082                   basic_block bb,
3083                   struct df_insn_info *insn_info,
3084                   int flags)
3085 {
3086   rtx note;
3087   bool is_sibling_call;
3088   unsigned int i;
3089   HARD_REG_SET defs_generated;
3090   HARD_REG_SET fn_reg_set_usage;
3091
3092   CLEAR_HARD_REG_SET (defs_generated);
3093   df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated);
3094   is_sibling_call = SIBLING_CALL_P (insn_info->insn);
3095   get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage,
3096                           regs_invalidated_by_call);
3097
3098   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3099     {
3100       if (i == STACK_POINTER_REGNUM)
3101         /* The stack ptr is used (honorarily) by a CALL insn.  */
3102         df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3103                        NULL, bb, insn_info, DF_REF_REG_USE,
3104                        DF_REF_CALL_STACK_USAGE | flags);
3105       else if (global_regs[i])
3106         {
3107           /* Calls to const functions cannot access any global registers and
3108              calls to pure functions cannot set them.  All other calls may
3109              reference any of the global registers, so they are recorded as
3110              used. */
3111           if (!RTL_CONST_CALL_P (insn_info->insn))
3112             {
3113               df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3114                              NULL, bb, insn_info, DF_REF_REG_USE, flags);
3115               if (!RTL_PURE_CALL_P (insn_info->insn))
3116                 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3117                                NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3118             }
3119         }
3120       else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i)
3121                /* no clobbers for regs that are the result of the call */
3122                && !TEST_HARD_REG_BIT (defs_generated, i)
3123                && (!is_sibling_call
3124                    || !bitmap_bit_p (df->exit_block_uses, i)
3125                    || refers_to_regno_p (i, crtl->return_rtx)))
3126           df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3127                          NULL, bb, insn_info, DF_REF_REG_DEF,
3128                          DF_REF_MAY_CLOBBER | flags);
3129     }
3130
3131   /* Record the registers used to pass arguments, and explicitly
3132      noted as clobbered.  */
3133   for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note;
3134        note = XEXP (note, 1))
3135     {
3136       if (GET_CODE (XEXP (note, 0)) == USE)
3137         df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0),
3138                         DF_REF_REG_USE, bb, insn_info, flags);
3139       else if (GET_CODE (XEXP (note, 0)) == CLOBBER)
3140         {
3141           if (REG_P (XEXP (XEXP (note, 0), 0)))
3142             {
3143               unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0));
3144               if (!TEST_HARD_REG_BIT (defs_generated, regno))
3145                 df_defs_record (collection_rec, XEXP (note, 0), bb,
3146                                 insn_info, flags);
3147             }
3148           else
3149             df_uses_record (collection_rec, &XEXP (note, 0),
3150                             DF_REF_REG_USE, bb, insn_info, flags);
3151         }
3152     }
3153
3154   return;
3155 }
3156
3157 /* Collect all refs in the INSN. This function is free of any
3158    side-effect - it will create and return a lists of df_ref's in the
3159    COLLECTION_REC without putting those refs into existing ref chains
3160    and reg chains. */
3161
3162 static void
3163 df_insn_refs_collect (struct df_collection_rec *collection_rec,
3164                       basic_block bb, struct df_insn_info *insn_info)
3165 {
3166   rtx note;
3167   bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC);
3168
3169   /* Clear out the collection record.  */
3170   collection_rec->def_vec.truncate (0);
3171   collection_rec->use_vec.truncate (0);
3172   collection_rec->eq_use_vec.truncate (0);
3173   collection_rec->mw_vec.truncate (0);
3174
3175   /* Process REG_EQUIV/REG_EQUAL notes.  */
3176   for (note = REG_NOTES (insn_info->insn); note;
3177        note = XEXP (note, 1))
3178     {
3179       switch (REG_NOTE_KIND (note))
3180         {
3181         case REG_EQUIV:
3182         case REG_EQUAL:
3183           df_uses_record (collection_rec,
3184                           &XEXP (note, 0), DF_REF_REG_USE,
3185                           bb, insn_info, DF_REF_IN_NOTE);
3186           break;
3187         case REG_NON_LOCAL_GOTO:
3188           /* The frame ptr is used by a non-local goto.  */
3189           df_ref_record (DF_REF_BASE, collection_rec,
3190                          regno_reg_rtx[FRAME_POINTER_REGNUM],
3191                          NULL, bb, insn_info,
3192                          DF_REF_REG_USE, 0);
3193           if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3194             df_ref_record (DF_REF_BASE, collection_rec,
3195                            regno_reg_rtx[HARD_FRAME_POINTER_REGNUM],
3196                            NULL, bb, insn_info,
3197                            DF_REF_REG_USE, 0);
3198           break;
3199         default:
3200           break;
3201         }
3202     }
3203
3204   int flags = (is_cond_exec) ? DF_REF_CONDITIONAL : 0;
3205   /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3206      uses from CALL_INSN_FUNCTION_USAGE. */
3207   if (CALL_P (insn_info->insn))
3208     df_get_call_refs (collection_rec, bb, insn_info, flags);
3209
3210   if (asm_noperands (PATTERN (insn_info->insn)) >= 0)
3211     for (unsigned i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3212       if (global_regs[i])
3213        {
3214          /* As with calls, asm statements reference all global regs. */
3215          df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3216                         NULL, bb, insn_info, DF_REF_REG_USE, flags);
3217          df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i],
3218                         NULL, bb, insn_info, DF_REF_REG_DEF, flags);
3219        }
3220
3221   /* Record other defs.  These should be mostly for DF_REF_REGULAR, so
3222      that a qsort on the defs is unnecessary in most cases.  */
3223   df_defs_record (collection_rec,
3224                   PATTERN (insn_info->insn), bb, insn_info, 0);
3225
3226   /* Record the register uses.  */
3227   df_uses_record (collection_rec,
3228                   &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0);
3229
3230   /* DF_REF_CONDITIONAL needs corresponding USES. */
3231   if (is_cond_exec)
3232     df_get_conditional_uses (collection_rec);
3233
3234   df_canonize_collection_rec (collection_rec);
3235 }
3236
3237 /* Recompute the luids for the insns in BB.  */
3238
3239 void
3240 df_recompute_luids (basic_block bb)
3241 {
3242   rtx_insn *insn;
3243   int luid = 0;
3244
3245   df_grow_insn_info ();
3246
3247   /* Scan the block an insn at a time from beginning to end.  */
3248   FOR_BB_INSNS (bb, insn)
3249     {
3250       struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3251       /* Inserting labels does not always trigger the incremental
3252          rescanning.  */
3253       if (!insn_info)
3254         {
3255           gcc_assert (!INSN_P (insn));
3256           insn_info = df_insn_create_insn_record (insn);
3257         }
3258
3259       DF_INSN_INFO_LUID (insn_info) = luid;
3260       if (INSN_P (insn))
3261         luid++;
3262     }
3263 }
3264
3265
3266 /* Collect all artificial refs at the block level for BB and add them
3267    to COLLECTION_REC.  */
3268
3269 static void
3270 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3271 {
3272   collection_rec->def_vec.truncate (0);
3273   collection_rec->use_vec.truncate (0);
3274   collection_rec->eq_use_vec.truncate (0);
3275   collection_rec->mw_vec.truncate (0);
3276
3277   if (bb->index == ENTRY_BLOCK)
3278     {
3279       df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3280       return;
3281     }
3282   else if (bb->index == EXIT_BLOCK)
3283     {
3284       df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3285       return;
3286     }
3287
3288   if (bb_has_eh_pred (bb))
3289     {
3290       unsigned int i;
3291       /* Mark the registers that will contain data for the handler.  */
3292       for (i = 0; ; ++i)
3293         {
3294           unsigned regno = EH_RETURN_DATA_REGNO (i);
3295           if (regno == INVALID_REGNUM)
3296             break;
3297           df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3298                          bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3299         }
3300     }
3301
3302   /* Add the hard_frame_pointer if this block is the target of a
3303      non-local goto.  */
3304   if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3305     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3306                    bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP);
3307
3308   /* Add the artificial uses.  */
3309   if (bb->index >= NUM_FIXED_BLOCKS)
3310     {
3311       bitmap_iterator bi;
3312       unsigned int regno;
3313       bitmap au = bb_has_eh_pred (bb)
3314         ? &df->eh_block_artificial_uses
3315         : &df->regular_block_artificial_uses;
3316
3317       EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3318         {
3319           df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3320                          bb, NULL, DF_REF_REG_USE, 0);
3321         }
3322     }
3323
3324   df_canonize_collection_rec (collection_rec);
3325 }
3326
3327
3328 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS.  */
3329
3330 void
3331 df_bb_refs_record (int bb_index, bool scan_insns)
3332 {
3333   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3334   rtx_insn *insn;
3335   int luid = 0;
3336
3337   if (!df)
3338     return;
3339
3340   df_collection_rec collection_rec;
3341   df_grow_bb_info (df_scan);
3342   if (scan_insns)
3343     /* Scan the block an insn at a time from beginning to end.  */
3344     FOR_BB_INSNS (bb, insn)
3345       {
3346         struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3347         gcc_assert (!insn_info);
3348
3349         insn_info = df_insn_create_insn_record (insn);
3350         if (INSN_P (insn))
3351           {
3352             /* Record refs within INSN.  */
3353             DF_INSN_INFO_LUID (insn_info) = luid++;
3354             df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3355             df_refs_add_to_chains (&collection_rec, bb, insn, copy_all);
3356           }
3357         DF_INSN_INFO_LUID (insn_info) = luid;
3358       }
3359
3360   /* Other block level artificial refs */
3361   df_bb_refs_collect (&collection_rec, bb);
3362   df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all);
3363
3364   /* Now that the block has been processed, set the block as dirty so
3365      LR and LIVE will get it processed.  */
3366   df_set_bb_dirty (bb);
3367 }
3368
3369
3370 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3371    block. */
3372
3373 static void
3374 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3375 {
3376 #ifdef EH_USES
3377   unsigned int i;
3378 #endif
3379
3380   bitmap_clear (regular_block_artificial_uses);
3381
3382   if (reload_completed)
3383     {
3384       if (frame_pointer_needed)
3385         bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3386     }
3387   else
3388     /* Before reload, there are a few registers that must be forced
3389        live everywhere -- which might not already be the case for
3390        blocks within infinite loops.  */
3391     {
3392       unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3393
3394       /* Any reference to any pseudo before reload is a potential
3395          reference of the frame pointer.  */
3396       bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3397
3398       if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3399         bitmap_set_bit (regular_block_artificial_uses,
3400                         HARD_FRAME_POINTER_REGNUM);
3401
3402       /* Pseudos with argument area equivalences may require
3403          reloading via the argument pointer.  */
3404       if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3405           && fixed_regs[ARG_POINTER_REGNUM])
3406         bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3407
3408       /* Any constant, or pseudo with constant equivalences, may
3409          require reloading from memory using the pic register.  */
3410       if (picreg != INVALID_REGNUM
3411           && fixed_regs[picreg])
3412         bitmap_set_bit (regular_block_artificial_uses, picreg);
3413     }
3414   /* The all-important stack pointer must always be live.  */
3415   bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3416
3417 #ifdef EH_USES
3418   /* EH_USES registers are used:
3419      1) at all insns that might throw (calls or with -fnon-call-exceptions
3420         trapping insns)
3421      2) in all EH edges
3422      3) to support backtraces and/or debugging, anywhere between their
3423         initialization and where they the saved registers are restored
3424         from them, including the cases where we don't reach the epilogue
3425         (noreturn call or infinite loop).  */
3426   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3427     if (EH_USES (i))
3428       bitmap_set_bit (regular_block_artificial_uses, i);
3429 #endif
3430 }
3431
3432
3433 /* Get the artificial use set for an eh block. */
3434
3435 static void
3436 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3437 {
3438   bitmap_clear (eh_block_artificial_uses);
3439
3440   /* The following code (down through the arg_pointer setting APPEARS
3441      to be necessary because there is nothing that actually
3442      describes what the exception handling code may actually need
3443      to keep alive.  */
3444   if (reload_completed)
3445     {
3446       if (frame_pointer_needed)
3447         {
3448           bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3449           if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
3450             bitmap_set_bit (eh_block_artificial_uses,
3451                             HARD_FRAME_POINTER_REGNUM);
3452         }
3453       if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3454           && fixed_regs[ARG_POINTER_REGNUM])
3455         bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3456     }
3457 }
3458
3459
3460 \f
3461 /*----------------------------------------------------------------------------
3462    Specialized hard register scanning functions.
3463 ----------------------------------------------------------------------------*/
3464
3465
3466 /* Mark a register in SET.  Hard registers in large modes get all
3467    of their component registers set as well.  */
3468
3469 static void
3470 df_mark_reg (rtx reg, void *vset)
3471 {
3472   bitmap_set_range ((bitmap) vset, REGNO (reg), REG_NREGS (reg));
3473 }
3474
3475
3476 /* Set the bit for regs that are considered being defined at the entry. */
3477
3478 static void
3479 df_get_entry_block_def_set (bitmap entry_block_defs)
3480 {
3481   rtx r;
3482   int i;
3483
3484   bitmap_clear (entry_block_defs);
3485
3486   /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3487      need a prologue for some component to be executed before that block,
3488      and we do not care about any other registers.  Hence, we do not want
3489      any register for any component defined in the entry block, and we can
3490      just leave all registers undefined.  */
3491   if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3492     return;
3493
3494   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3495     {
3496       if (global_regs[i])
3497         bitmap_set_bit (entry_block_defs, i);
3498       if (FUNCTION_ARG_REGNO_P (i))
3499         bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3500     }
3501
3502   /* The always important stack pointer.  */
3503   bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3504
3505   /* Once the prologue has been generated, all of these registers
3506      should just show up in the first regular block.  */
3507   if (targetm.have_prologue () && epilogue_completed)
3508     {
3509       /* Defs for the callee saved registers are inserted so that the
3510          pushes have some defining location.  */
3511       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3512         if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3513           bitmap_set_bit (entry_block_defs, i);
3514     }
3515
3516   r = targetm.calls.struct_value_rtx (current_function_decl, true);
3517   if (r && REG_P (r))
3518     bitmap_set_bit (entry_block_defs, REGNO (r));
3519
3520   /* If the function has an incoming STATIC_CHAIN, it has to show up
3521      in the entry def set.  */
3522   r = rtx_for_static_chain (current_function_decl, true);
3523   if (r && REG_P (r))
3524     bitmap_set_bit (entry_block_defs, REGNO (r));
3525
3526   if ((!reload_completed) || frame_pointer_needed)
3527     {
3528       /* Any reference to any pseudo before reload is a potential
3529          reference of the frame pointer.  */
3530       bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3531
3532       /* If they are different, also mark the hard frame pointer as live.  */
3533       if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3534           && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3535         bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3536     }
3537
3538   /* These registers are live everywhere.  */
3539   if (!reload_completed)
3540     {
3541       /* Pseudos with argument area equivalences may require
3542          reloading via the argument pointer.  */
3543       if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3544           && fixed_regs[ARG_POINTER_REGNUM])
3545         bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3546
3547       /* Any constant, or pseudo with constant equivalences, may
3548          require reloading from memory using the pic register.  */
3549       unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3550       if (picreg != INVALID_REGNUM
3551           && fixed_regs[picreg])
3552         bitmap_set_bit (entry_block_defs, picreg);
3553     }
3554
3555 #ifdef INCOMING_RETURN_ADDR_RTX
3556   if (REG_P (INCOMING_RETURN_ADDR_RTX))
3557     bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3558 #endif
3559
3560   targetm.extra_live_on_entry (entry_block_defs);
3561 }
3562
3563
3564 /* Return the (conservative) set of hard registers that are defined on
3565    entry to the function.
3566    It uses df->entry_block_defs to determine which register
3567    reference to include.  */
3568
3569 static void
3570 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3571                              bitmap entry_block_defs)
3572 {
3573   unsigned int i;
3574   bitmap_iterator bi;
3575
3576   EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3577     {
3578       df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3579                      ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0);
3580     }
3581
3582   df_canonize_collection_rec (collection_rec);
3583 }
3584
3585
3586 /* Record the (conservative) set of hard registers that are defined on
3587    entry to the function.  */
3588
3589 static void
3590 df_record_entry_block_defs (bitmap entry_block_defs)
3591 {
3592   struct df_collection_rec collection_rec;
3593   df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3594
3595   /* Process bb_refs chain */
3596   df_refs_add_to_chains (&collection_rec,
3597                          BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK),
3598                          NULL,
3599                          copy_defs);
3600 }
3601
3602
3603 /* Update the defs in the entry block.  */
3604
3605 void
3606 df_update_entry_block_defs (void)
3607 {
3608   bool changed = false;
3609
3610   auto_bitmap refs (&df_bitmap_obstack);
3611   df_get_entry_block_def_set (refs);
3612   if (df->entry_block_defs)
3613     {
3614       if (!bitmap_equal_p (df->entry_block_defs, refs))
3615         {
3616           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3617           df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3618           df_ref_chain_delete (bb_info->artificial_defs);
3619           bb_info->artificial_defs = NULL;
3620           changed = true;
3621         }
3622     }
3623   else
3624     {
3625       struct df_scan_problem_data *problem_data
3626         = (struct df_scan_problem_data *) df_scan->problem_data;
3627         gcc_unreachable ();
3628       df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3629       changed = true;
3630     }
3631
3632   if (changed)
3633     {
3634       df_record_entry_block_defs (refs);
3635       bitmap_copy (df->entry_block_defs, refs);
3636       df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK));
3637     }
3638 }
3639
3640
3641 /* Set the bit for regs that are considered being used at the exit. */
3642
3643 static void
3644 df_get_exit_block_use_set (bitmap exit_block_uses)
3645 {
3646   unsigned int i;
3647   unsigned int picreg = PIC_OFFSET_TABLE_REGNUM;
3648
3649   bitmap_clear (exit_block_uses);
3650
3651   /* For separate shrink-wrapping we use LIVE to analyze which basic blocks
3652      need an epilogue for some component to be executed after that block,
3653      and we do not care about any other registers.  Hence, we do not want
3654      any register for any component seen as used in the exit block, and we
3655      can just say no registers at all are used.  */
3656   if (df_scan->local_flags & DF_SCAN_EMPTY_ENTRY_EXIT)
3657     return;
3658
3659   /* Stack pointer is always live at the exit.  */
3660   bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
3661
3662   /* Mark the frame pointer if needed at the end of the function.
3663      If we end up eliminating it, it will be removed from the live
3664      list of each basic block by reload.  */
3665
3666   if ((!reload_completed) || frame_pointer_needed)
3667     {
3668       bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
3669
3670       /* If they are different, also mark the hard frame pointer as live.  */
3671       if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3672           && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3673         bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
3674     }
3675
3676   /* Many architectures have a GP register even without flag_pic.
3677      Assume the pic register is not in use, or will be handled by
3678      other means, if it is not fixed.  */
3679   if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3680       && picreg != INVALID_REGNUM
3681       && fixed_regs[picreg])
3682     bitmap_set_bit (exit_block_uses, picreg);
3683
3684   /* Mark all global registers, and all registers used by the
3685      epilogue as being live at the end of the function since they
3686      may be referenced by our caller.  */
3687   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3688     if (global_regs[i] || EPILOGUE_USES (i))
3689       bitmap_set_bit (exit_block_uses, i);
3690
3691   if (targetm.have_epilogue () && epilogue_completed)
3692     {
3693       /* Mark all call-saved registers that we actually used.  */
3694       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3695         if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
3696             && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3697           bitmap_set_bit (exit_block_uses, i);
3698     }
3699
3700   /* Mark the registers that will contain data for the handler.  */
3701   if (reload_completed && crtl->calls_eh_return)
3702     for (i = 0; ; ++i)
3703       {
3704         unsigned regno = EH_RETURN_DATA_REGNO (i);
3705         if (regno == INVALID_REGNUM)
3706           break;
3707         bitmap_set_bit (exit_block_uses, regno);
3708       }
3709
3710 #ifdef EH_RETURN_STACKADJ_RTX
3711   if ((!targetm.have_epilogue () || ! epilogue_completed)
3712       && crtl->calls_eh_return)
3713     {
3714       rtx tmp = EH_RETURN_STACKADJ_RTX;
3715       if (tmp && REG_P (tmp))
3716         df_mark_reg (tmp, exit_block_uses);
3717     }
3718 #endif
3719
3720   if ((!targetm.have_epilogue () || ! epilogue_completed)
3721       && crtl->calls_eh_return)
3722     {
3723       rtx tmp = EH_RETURN_HANDLER_RTX;
3724       if (tmp && REG_P (tmp))
3725         df_mark_reg (tmp, exit_block_uses);
3726     }
3727
3728   /* Mark function return value.  */
3729   diddle_return_value (df_mark_reg, (void*) exit_block_uses);
3730 }
3731
3732
3733 /* Return the refs of hard registers that are used in the exit block.
3734    It uses df->exit_block_uses to determine register to include.  */
3735
3736 static void
3737 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
3738 {
3739   unsigned int i;
3740   bitmap_iterator bi;
3741
3742   EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
3743     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3744                    EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3745
3746   /* It is deliberate that this is not put in the exit block uses but
3747      I do not know why.  */
3748   if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3749       && reload_completed
3750       && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
3751       && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun))
3752       && fixed_regs[ARG_POINTER_REGNUM])
3753     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
3754                    EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0);
3755
3756   df_canonize_collection_rec (collection_rec);
3757 }
3758
3759
3760 /* Record the set of hard registers that are used in the exit block.
3761    It uses df->exit_block_uses to determine which bit to include.  */
3762
3763 static void
3764 df_record_exit_block_uses (bitmap exit_block_uses)
3765 {
3766   struct df_collection_rec collection_rec;
3767   df_exit_block_uses_collect (&collection_rec, exit_block_uses);
3768
3769   /* Process bb_refs chain */
3770   df_refs_add_to_chains (&collection_rec,
3771                          BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK),
3772                          NULL,
3773                          copy_uses);
3774 }
3775
3776
3777 /* Update the uses in the exit block.  */
3778
3779 void
3780 df_update_exit_block_uses (void)
3781 {
3782   bool changed = false;
3783
3784   auto_bitmap refs (&df_bitmap_obstack);
3785   df_get_exit_block_use_set (refs);
3786   if (df->exit_block_uses)
3787     {
3788       if (!bitmap_equal_p (df->exit_block_uses, refs))
3789         {
3790           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
3791           df_ref_chain_delete_du_chain (bb_info->artificial_uses);
3792           df_ref_chain_delete (bb_info->artificial_uses);
3793           bb_info->artificial_uses = NULL;
3794           changed = true;
3795         }
3796     }
3797   else
3798     {
3799       struct df_scan_problem_data *problem_data
3800         = (struct df_scan_problem_data *) df_scan->problem_data;
3801         gcc_unreachable ();
3802       df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3803       changed = true;
3804     }
3805
3806   if (changed)
3807     {
3808       df_record_exit_block_uses (refs);
3809       bitmap_copy (df->exit_block_uses, refs);
3810       df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK));
3811     }
3812 }
3813
3814 static bool initialized = false;
3815
3816
3817 /* Initialize some platform specific structures.  */
3818
3819 void
3820 df_hard_reg_init (void)
3821 {
3822   int i;
3823   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
3824
3825   if (initialized)
3826     return;
3827
3828   /* Record which registers will be eliminated.  We use this in
3829      mark_used_regs.  */
3830   CLEAR_HARD_REG_SET (elim_reg_set);
3831
3832   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
3833     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
3834
3835   initialized = true;
3836 }
3837
3838
3839 /* Recompute the parts of scanning that are based on regs_ever_live
3840    because something changed in that array.  */
3841
3842 void
3843 df_update_entry_exit_and_calls (void)
3844 {
3845   basic_block bb;
3846
3847   df_update_entry_block_defs ();
3848   df_update_exit_block_uses ();
3849
3850   /* The call insns need to be rescanned because there may be changes
3851      in the set of registers clobbered across the call.  */
3852   FOR_EACH_BB_FN (bb, cfun)
3853     {
3854       rtx_insn *insn;
3855       FOR_BB_INSNS (bb, insn)
3856         {
3857           if (INSN_P (insn) && CALL_P (insn))
3858             df_insn_rescan (insn);
3859         }
3860     }
3861 }
3862
3863
3864 /* Return true if hard REG is actually used in the some instruction.
3865    There are a fair number of conditions that affect the setting of
3866    this array.  See the comment in df.h for df->hard_regs_live_count
3867    for the conditions that this array is set. */
3868
3869 bool
3870 df_hard_reg_used_p (unsigned int reg)
3871 {
3872   return df->hard_regs_live_count[reg] != 0;
3873 }
3874
3875
3876 /* A count of the number of times REG is actually used in the some
3877    instruction.  There are a fair number of conditions that affect the
3878    setting of this array.  See the comment in df.h for
3879    df->hard_regs_live_count for the conditions that this array is
3880    set. */
3881
3882
3883 unsigned int
3884 df_hard_reg_used_count (unsigned int reg)
3885 {
3886   return df->hard_regs_live_count[reg];
3887 }
3888
3889
3890 /* Get the value of regs_ever_live[REGNO].  */
3891
3892 bool
3893 df_regs_ever_live_p (unsigned int regno)
3894 {
3895   return regs_ever_live[regno];
3896 }
3897
3898
3899 /* Set regs_ever_live[REGNO] to VALUE.  If this cause regs_ever_live
3900    to change, schedule that change for the next update.  */
3901
3902 void
3903 df_set_regs_ever_live (unsigned int regno, bool value)
3904 {
3905   if (regs_ever_live[regno] == value)
3906     return;
3907
3908   regs_ever_live[regno] = value;
3909   if (df)
3910     df->redo_entry_and_exit = true;
3911 }
3912
3913
3914 /* Compute "regs_ever_live" information from the underlying df
3915    information.  Set the vector to all false if RESET.  */
3916
3917 void
3918 df_compute_regs_ever_live (bool reset)
3919 {
3920   unsigned int i;
3921   bool changed = df->redo_entry_and_exit;
3922
3923   if (reset)
3924     memset (regs_ever_live, 0, sizeof (regs_ever_live));
3925
3926   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3927     if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
3928       {
3929         regs_ever_live[i] = true;
3930         changed = true;
3931       }
3932   if (changed)
3933     df_update_entry_exit_and_calls ();
3934   df->redo_entry_and_exit = false;
3935 }
3936
3937 \f
3938 /*----------------------------------------------------------------------------
3939   Dataflow ref information verification functions.
3940
3941   df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3942   df_reg_chain_verify_unmarked (refs)
3943   df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3944   df_mws_verify (mw*, mw*, bool)
3945   df_insn_refs_verify (collection_rec, bb, insn, bool)
3946   df_bb_refs_verify (bb, refs, bool)
3947   df_bb_verify (bb)
3948   df_exit_block_bitmap_verify (bool)
3949   df_entry_block_bitmap_verify (bool)
3950   df_scan_verify ()
3951 ----------------------------------------------------------------------------*/
3952
3953
3954 /* Mark all refs in the reg chain.  Verify that all of the registers
3955 are in the correct chain.  */
3956
3957 static unsigned int
3958 df_reg_chain_mark (df_ref refs, unsigned int regno,
3959                    bool is_def, bool is_eq_use)
3960 {
3961   unsigned int count = 0;
3962   df_ref ref;
3963   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
3964     {
3965       gcc_assert (!DF_REF_IS_REG_MARKED (ref));
3966
3967       /* If there are no def-use or use-def chains, make sure that all
3968          of the chains are clear.  */
3969       if (!df_chain)
3970         gcc_assert (!DF_REF_CHAIN (ref));
3971
3972       /* Check to make sure the ref is in the correct chain.  */
3973       gcc_assert (DF_REF_REGNO (ref) == regno);
3974       if (is_def)
3975         gcc_assert (DF_REF_REG_DEF_P (ref));
3976       else
3977         gcc_assert (!DF_REF_REG_DEF_P (ref));
3978
3979       if (is_eq_use)
3980         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
3981       else
3982         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
3983
3984       if (DF_REF_NEXT_REG (ref))
3985         gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
3986       count++;
3987       DF_REF_REG_MARK (ref);
3988     }
3989   return count;
3990 }
3991
3992
3993 /* Verify that all of the registers in the chain are unmarked.  */
3994
3995 static void
3996 df_reg_chain_verify_unmarked (df_ref refs)
3997 {
3998   df_ref ref;
3999   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4000     gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4001 }
4002
4003
4004 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4005
4006 static bool
4007 df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
4008                 bool abort_if_fail)
4009 {
4010   unsigned int ix;
4011   df_ref new_ref;
4012
4013   FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
4014     {
4015       if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
4016         {
4017           if (abort_if_fail)
4018             gcc_assert (0);
4019           else
4020             return false;
4021         }
4022
4023       /* Abort if fail is called from the function level verifier.  If
4024          that is the context, mark this reg as being seem.  */
4025       if (abort_if_fail)
4026         {
4027           gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
4028           DF_REF_REG_UNMARK (old_rec);
4029         }
4030
4031       old_rec = DF_REF_NEXT_LOC (old_rec);
4032     }
4033
4034   if (abort_if_fail)
4035     gcc_assert (old_rec == NULL);
4036   else
4037     return old_rec == NULL;
4038   return false;
4039 }
4040
4041
4042 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4043
4044 static bool
4045 df_mws_verify (const vec<df_mw_hardreg *, va_heap> *new_rec,
4046                struct df_mw_hardreg *old_rec,
4047                bool abort_if_fail)
4048 {
4049   unsigned int ix;
4050   struct df_mw_hardreg *new_reg;
4051
4052   FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
4053     {
4054       if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
4055         {
4056           if (abort_if_fail)
4057             gcc_assert (0);
4058           else
4059             return false;
4060         }
4061       old_rec = DF_MWS_NEXT (old_rec);
4062     }
4063
4064   if (abort_if_fail)
4065     gcc_assert (old_rec == NULL);
4066   else
4067     return old_rec == NULL;
4068   return false;
4069 }
4070
4071
4072 /* Return true if the existing insn refs information is complete and
4073    correct. Otherwise (i.e. if there's any missing or extra refs),
4074    return the correct df_ref chain in REFS_RETURN.
4075
4076    If ABORT_IF_FAIL, leave the refs that are verified (already in the
4077    ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4078    verification mode instead of the whole function, so unmark
4079    everything.
4080
4081    If ABORT_IF_FAIL is set, this function never returns false.  */
4082
4083 static bool
4084 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4085                      basic_block bb,
4086                      rtx_insn *insn,
4087                      bool abort_if_fail)
4088 {
4089   bool ret1, ret2, ret3;
4090   unsigned int uid = INSN_UID (insn);
4091   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4092
4093   df_insn_refs_collect (collection_rec, bb, insn_info);
4094
4095   /* Unfortunately we cannot opt out early if one of these is not
4096      right and abort_if_fail is set because the marks will not get cleared.  */
4097   ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4098                          abort_if_fail);
4099   if (!ret1 && !abort_if_fail)
4100     return false;
4101   ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid),
4102                          abort_if_fail);
4103   if (!ret2 && !abort_if_fail)
4104     return false;
4105   ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4106                          abort_if_fail);
4107   if (!ret3 && !abort_if_fail)
4108     return false;
4109   if (! df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4110                        abort_if_fail))
4111     return false;
4112   return (ret1 && ret2 && ret3);
4113 }
4114
4115
4116 /* Return true if all refs in the basic block are correct and complete.
4117    Due to df_ref_chain_verify, it will cause all refs
4118    that are verified to have DF_REF_MARK bit set.  */
4119
4120 static bool
4121 df_bb_verify (basic_block bb)
4122 {
4123   rtx_insn *insn;
4124   struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4125   struct df_collection_rec collection_rec;
4126
4127   gcc_assert (bb_info);
4128
4129   /* Scan the block, one insn at a time, from beginning to end.  */
4130   FOR_BB_INSNS_REVERSE (bb, insn)
4131     {
4132       if (!INSN_P (insn))
4133         continue;
4134       df_insn_refs_verify (&collection_rec, bb, insn, true);
4135       df_free_collection_rec (&collection_rec);
4136     }
4137
4138   /* Do the artificial defs and uses.  */
4139   df_bb_refs_collect (&collection_rec, bb);
4140   df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4141   df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4142   df_free_collection_rec (&collection_rec);
4143
4144   return true;
4145 }
4146
4147
4148 /* Returns true if the entry block has correct and complete df_ref set.
4149    If not it either aborts if ABORT_IF_FAIL is true or returns false.  */
4150
4151 static bool
4152 df_entry_block_bitmap_verify (bool abort_if_fail)
4153 {
4154   bool is_eq;
4155
4156   auto_bitmap entry_block_defs (&df_bitmap_obstack);
4157   df_get_entry_block_def_set (entry_block_defs);
4158
4159   is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4160
4161   if (!is_eq && abort_if_fail)
4162     {
4163       fprintf (stderr, "entry_block_defs = ");
4164       df_print_regset (stderr, entry_block_defs);
4165       fprintf (stderr, "df->entry_block_defs = ");
4166       df_print_regset (stderr, df->entry_block_defs);
4167       gcc_assert (0);
4168     }
4169
4170   return is_eq;
4171 }
4172
4173
4174 /* Returns true if the exit block has correct and complete df_ref set.
4175    If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4176
4177 static bool
4178 df_exit_block_bitmap_verify (bool abort_if_fail)
4179 {
4180   bool is_eq;
4181
4182   auto_bitmap exit_block_uses (&df_bitmap_obstack);
4183   df_get_exit_block_use_set (exit_block_uses);
4184
4185   is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4186
4187   if (!is_eq && abort_if_fail)
4188     {
4189       fprintf (stderr, "exit_block_uses = ");
4190       df_print_regset (stderr, exit_block_uses);
4191       fprintf (stderr, "df->exit_block_uses = ");
4192       df_print_regset (stderr, df->exit_block_uses);
4193       gcc_assert (0);
4194     }
4195
4196   return is_eq;
4197 }
4198
4199
4200 /* Return true if df_ref information for all insns in all blocks are
4201    correct and complete.  */
4202
4203 void
4204 df_scan_verify (void)
4205 {
4206   unsigned int i;
4207   basic_block bb;
4208
4209   if (!df)
4210     return;
4211
4212   /* Verification is a 4 step process. */
4213
4214   /* (1) All of the refs are marked by going through the reg chains.  */
4215   for (i = 0; i < DF_REG_SIZE (df); i++)
4216     {
4217       gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4218                   == DF_REG_DEF_COUNT (i));
4219       gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4220                   == DF_REG_USE_COUNT (i));
4221       gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4222                   == DF_REG_EQ_USE_COUNT (i));
4223     }
4224
4225   /* (2) There are various bitmaps whose value may change over the
4226      course of the compilation.  This step recomputes them to make
4227      sure that they have not slipped out of date.  */
4228   auto_bitmap regular_block_artificial_uses (&df_bitmap_obstack);
4229   auto_bitmap eh_block_artificial_uses (&df_bitmap_obstack);
4230
4231   df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4232   df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4233
4234   bitmap_ior_into (eh_block_artificial_uses,
4235                    regular_block_artificial_uses);
4236
4237   /* Check artificial_uses bitmaps didn't change. */
4238   gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4239                               &df->regular_block_artificial_uses));
4240   gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4241                               &df->eh_block_artificial_uses));
4242
4243   /* Verify entry block and exit block. These only verify the bitmaps,
4244      the refs are verified in df_bb_verify.  */
4245   df_entry_block_bitmap_verify (true);
4246   df_exit_block_bitmap_verify (true);
4247
4248   /* (3) All of the insns in all of the blocks are traversed and the
4249      marks are cleared both in the artificial refs attached to the
4250      blocks and the real refs inside the insns.  It is a failure to
4251      clear a mark that has not been set as this means that the ref in
4252      the block or insn was not in the reg chain.  */
4253
4254   FOR_ALL_BB_FN (bb, cfun)
4255     df_bb_verify (bb);
4256
4257   /* (4) See if all reg chains are traversed a second time.  This time
4258      a check is made that the marks are clear. A set mark would be a
4259      from a reg that is not in any insn or basic block.  */
4260
4261   for (i = 0; i < DF_REG_SIZE (df); i++)
4262     {
4263       df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4264       df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4265       df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4266     }
4267 }