gcc/df-scan.c

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