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