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