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