gcc/df-scan.c

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