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 /* Collect all artificial refs at the block level for BB and add them
3605    to COLLECTION_REC.  */
3606
3607 static void
3608 df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb)
3609 {
3610   VEC_truncate (df_ref, collection_rec->def_vec, 0);
3611   VEC_truncate (df_ref, collection_rec->use_vec, 0);
3612   VEC_truncate (df_ref, collection_rec->eq_use_vec, 0);
3613   VEC_truncate (df_mw_hardreg_ptr, collection_rec->mw_vec, 0);
3614
3615   if (bb->index == ENTRY_BLOCK)
3616     {
3617       df_entry_block_defs_collect (collection_rec, df->entry_block_defs);
3618       return;
3619     }
3620   else if (bb->index == EXIT_BLOCK)
3621     {
3622       df_exit_block_uses_collect (collection_rec, df->exit_block_uses);
3623       return;
3624     }
3625
3626 #ifdef EH_RETURN_DATA_REGNO
3627   if (bb_has_eh_pred (bb))
3628     {
3629       unsigned int i;
3630       /* Mark the registers that will contain data for the handler.  */
3631       for (i = 0; ; ++i)
3632         {
3633           unsigned regno = EH_RETURN_DATA_REGNO (i);
3634           if (regno == INVALID_REGNUM)
3635             break;
3636           df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3637                          bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP, -1, -1,
3638                          VOIDmode);
3639         }
3640     }
3641 #endif
3642
3643   /* Add the hard_frame_pointer if this block is the target of a
3644      non-local goto.  */
3645   if (bb->flags & BB_NON_LOCAL_GOTO_TARGET)
3646     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL,
3647                    bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP, -1, -1, VOIDmode);
3648
3649   /* Add the artificial uses.  */
3650   if (bb->index >= NUM_FIXED_BLOCKS)
3651     {
3652       bitmap_iterator bi;
3653       unsigned int regno;
3654       bitmap au = bb_has_eh_pred (bb)
3655         ? df->eh_block_artificial_uses
3656         : df->regular_block_artificial_uses;
3657
3658       EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi)
3659         {
3660           df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL,
3661                          bb, NULL, DF_REF_REG_USE, 0, -1, -1, VOIDmode);
3662         }
3663     }
3664
3665   df_canonize_collection_rec (collection_rec);
3666 }
3667
3668
3669 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS.  */
3670
3671 void
3672 df_bb_refs_record (int bb_index, bool scan_insns)
3673 {
3674   basic_block bb = BASIC_BLOCK (bb_index);
3675   rtx insn;
3676   int luid = 0;
3677   struct df_scan_bb_info *bb_info;
3678   struct df_collection_rec collection_rec;
3679
3680   if (!df)
3681     return;
3682
3683   bb_info = df_scan_get_bb_info (bb_index);
3684
3685   /* Need to make sure that there is a record in the basic block info. */
3686   if (!bb_info)
3687     {
3688       bb_info = (struct df_scan_bb_info *) pool_alloc (df_scan->block_pool);
3689       df_scan_set_bb_info (bb_index, bb_info);
3690       bb_info->artificial_defs = NULL;
3691       bb_info->artificial_uses = NULL;
3692     }
3693
3694   collection_rec.def_vec = VEC_alloc (df_ref, stack, 128);
3695   collection_rec.use_vec = VEC_alloc (df_ref, stack, 32);
3696   collection_rec.eq_use_vec = VEC_alloc (df_ref, stack, 32);
3697   collection_rec.mw_vec = VEC_alloc (df_mw_hardreg_ptr, stack, 32);
3698
3699   if (scan_insns)
3700     /* Scan the block an insn at a time from beginning to end.  */
3701     FOR_BB_INSNS (bb, insn)
3702       {
3703         struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3704         gcc_assert (!insn_info);
3705
3706         insn_info = df_insn_create_insn_record (insn);
3707         if (INSN_P (insn))
3708           {
3709             /* Record refs within INSN.  */
3710             DF_INSN_INFO_LUID (insn_info) = luid++;
3711             df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn));
3712             df_refs_add_to_chains (&collection_rec, bb, insn);
3713           }
3714         DF_INSN_INFO_LUID (insn_info) = luid;
3715       }
3716
3717   /* Other block level artificial refs */
3718   df_bb_refs_collect (&collection_rec, bb);
3719   df_refs_add_to_chains (&collection_rec, bb, NULL);
3720
3721   VEC_free (df_ref, stack, collection_rec.def_vec);
3722   VEC_free (df_ref, stack, collection_rec.use_vec);
3723   VEC_free (df_ref, stack, collection_rec.eq_use_vec);
3724   VEC_free (df_mw_hardreg_ptr, stack, collection_rec.mw_vec);
3725
3726   /* Now that the block has been processed, set the block as dirty so
3727      LR and LIVE will get it processed.  */
3728   df_set_bb_dirty (bb);
3729 }
3730
3731
3732 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3733    block. */
3734
3735 static void
3736 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses)
3737 {
3738 #ifdef EH_USES
3739   unsigned int i;
3740 #endif
3741
3742   bitmap_clear (regular_block_artificial_uses);
3743
3744   if (reload_completed)
3745     {
3746       if (frame_pointer_needed)
3747         bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3748     }
3749   else
3750     /* Before reload, there are a few registers that must be forced
3751        live everywhere -- which might not already be the case for
3752        blocks within infinite loops.  */
3753     {
3754       /* Any reference to any pseudo before reload is a potential
3755          reference of the frame pointer.  */
3756       bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM);
3757
3758 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3759       bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3760 #endif
3761
3762 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3763       /* Pseudos with argument area equivalences may require
3764          reloading via the argument pointer.  */
3765       if (fixed_regs[ARG_POINTER_REGNUM])
3766         bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM);
3767 #endif
3768
3769       /* Any constant, or pseudo with constant equivalences, may
3770          require reloading from memory using the pic register.  */
3771       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3772           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3773         bitmap_set_bit (regular_block_artificial_uses, PIC_OFFSET_TABLE_REGNUM);
3774     }
3775   /* The all-important stack pointer must always be live.  */
3776   bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM);
3777
3778 #ifdef EH_USES
3779   /* EH_USES registers are used:
3780      1) at all insns that might throw (calls or with -fnon-call-exceptions
3781         trapping insns)
3782      2) in all EH edges
3783      3) to support backtraces and/or debugging, anywhere between their
3784         initialization and where they the saved registers are restored
3785         from them, including the cases where we don't reach the epilogue
3786         (noreturn call or infinite loop).  */
3787   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3788     if (EH_USES (i))
3789       bitmap_set_bit (regular_block_artificial_uses, i);
3790 #endif
3791 }
3792
3793
3794 /* Get the artificial use set for an eh block. */
3795
3796 static void
3797 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses)
3798 {
3799   bitmap_clear (eh_block_artificial_uses);
3800
3801   /* The following code (down thru the arg_pointer setting APPEARS
3802      to be necessary because there is nothing that actually
3803      describes what the exception handling code may actually need
3804      to keep alive.  */
3805   if (reload_completed)
3806     {
3807       if (frame_pointer_needed)
3808         {
3809           bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM);
3810 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3811           bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM);
3812 #endif
3813         }
3814 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3815       if (fixed_regs[ARG_POINTER_REGNUM])
3816         bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM);
3817 #endif
3818     }
3819 }
3820
3821
3822 \f
3823 /*----------------------------------------------------------------------------
3824    Specialized hard register scanning functions.
3825 ----------------------------------------------------------------------------*/
3826
3827
3828 /* Mark a register in SET.  Hard registers in large modes get all
3829    of their component registers set as well.  */
3830
3831 static void
3832 df_mark_reg (rtx reg, void *vset)
3833 {
3834   bitmap set = (bitmap) vset;
3835   int regno = REGNO (reg);
3836
3837   gcc_assert (GET_MODE (reg) != BLKmode);
3838
3839   bitmap_set_bit (set, regno);
3840   if (regno < FIRST_PSEUDO_REGISTER)
3841     {
3842       int n = hard_regno_nregs[regno][GET_MODE (reg)];
3843       while (--n > 0)
3844         bitmap_set_bit  (set, regno + n);
3845     }
3846 }
3847
3848
3849 /* Set the bit for regs that are considered being defined at the entry. */
3850
3851 static void
3852 df_get_entry_block_def_set (bitmap entry_block_defs)
3853 {
3854   rtx r;
3855   int i;
3856
3857   bitmap_clear (entry_block_defs);
3858
3859   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3860     {
3861       if (FUNCTION_ARG_REGNO_P (i))
3862 #ifdef INCOMING_REGNO
3863         bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i));
3864 #else
3865         bitmap_set_bit (entry_block_defs, i);
3866 #endif
3867     }
3868
3869   /* The always important stack pointer.  */
3870   bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM);
3871
3872   /* Once the prologue has been generated, all of these registers
3873      should just show up in the first regular block.  */
3874   if (HAVE_prologue && epilogue_completed)
3875     {
3876       /* Defs for the callee saved registers are inserted so that the
3877          pushes have some defining location.  */
3878       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3879         if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i)))
3880           bitmap_set_bit (entry_block_defs, i);
3881     }
3882
3883   r = targetm.calls.struct_value_rtx (current_function_decl, true);
3884   if (r && REG_P (r))
3885     bitmap_set_bit (entry_block_defs, REGNO (r));
3886
3887   /* If the function has an incoming STATIC_CHAIN, it has to show up
3888      in the entry def set.  */
3889   r = targetm.calls.static_chain (current_function_decl, true);
3890   if (r && REG_P (r))
3891     bitmap_set_bit (entry_block_defs, REGNO (r));
3892
3893   if ((!reload_completed) || frame_pointer_needed)
3894     {
3895       /* Any reference to any pseudo before reload is a potential
3896          reference of the frame pointer.  */
3897       bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM);
3898 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
3899       /* If they are different, also mark the hard frame pointer as live.  */
3900       if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
3901         bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM);
3902 #endif
3903     }
3904
3905   /* These registers are live everywhere.  */
3906   if (!reload_completed)
3907     {
3908 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3909       /* Pseudos with argument area equivalences may require
3910          reloading via the argument pointer.  */
3911       if (fixed_regs[ARG_POINTER_REGNUM])
3912         bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM);
3913 #endif
3914
3915 #ifdef PIC_OFFSET_TABLE_REGNUM
3916       /* Any constant, or pseudo with constant equivalences, may
3917          require reloading from memory using the pic register.  */
3918       if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
3919           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
3920         bitmap_set_bit (entry_block_defs, PIC_OFFSET_TABLE_REGNUM);
3921 #endif
3922     }
3923
3924 #ifdef INCOMING_RETURN_ADDR_RTX
3925   if (REG_P (INCOMING_RETURN_ADDR_RTX))
3926     bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX));
3927 #endif
3928
3929   targetm.live_on_entry (entry_block_defs);
3930 }
3931
3932
3933 /* Return the (conservative) set of hard registers that are defined on
3934    entry to the function.
3935    It uses df->entry_block_defs to determine which register
3936    reference to include.  */
3937
3938 static void
3939 df_entry_block_defs_collect (struct df_collection_rec *collection_rec,
3940                              bitmap entry_block_defs)
3941 {
3942   unsigned int i;
3943   bitmap_iterator bi;
3944
3945   EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi)
3946     {
3947       df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
3948                      ENTRY_BLOCK_PTR, NULL, DF_REF_REG_DEF, 0, -1, -1,
3949                      VOIDmode);
3950     }
3951
3952   df_canonize_collection_rec (collection_rec);
3953 }
3954
3955
3956 /* Record the (conservative) set of hard registers that are defined on
3957    entry to the function.  */
3958
3959 static void
3960 df_record_entry_block_defs (bitmap entry_block_defs)
3961 {
3962   struct df_collection_rec collection_rec;
3963   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
3964   collection_rec.def_vec = VEC_alloc (df_ref, stack, FIRST_PSEUDO_REGISTER);
3965   df_entry_block_defs_collect (&collection_rec, entry_block_defs);
3966
3967   /* Process bb_refs chain */
3968   df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (ENTRY_BLOCK), NULL);
3969   VEC_free (df_ref, stack, collection_rec.def_vec);
3970 }
3971
3972
3973 /* Update the defs in the entry block.  */
3974
3975 void
3976 df_update_entry_block_defs (void)
3977 {
3978   bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
3979   bool changed = false;
3980
3981   df_get_entry_block_def_set (refs);
3982   if (df->entry_block_defs)
3983     {
3984       if (!bitmap_equal_p (df->entry_block_defs, refs))
3985         {
3986           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK);
3987           df_ref_chain_delete_du_chain (bb_info->artificial_defs);
3988           df_ref_chain_delete (bb_info->artificial_defs);
3989           bb_info->artificial_defs = NULL;
3990           changed = true;
3991         }
3992     }
3993   else
3994     {
3995       struct df_scan_problem_data *problem_data
3996         = (struct df_scan_problem_data *) df_scan->problem_data;
3997       df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps);
3998       changed = true;
3999     }
4000
4001   if (changed)
4002     {
4003       df_record_entry_block_defs (refs);
4004       bitmap_copy (df->entry_block_defs, refs);
4005       df_set_bb_dirty (BASIC_BLOCK (ENTRY_BLOCK));
4006     }
4007   BITMAP_FREE (refs);
4008 }
4009
4010
4011 /* Set the bit for regs that are considered being used at the exit. */
4012
4013 static void
4014 df_get_exit_block_use_set (bitmap exit_block_uses)
4015 {
4016   unsigned int i;
4017
4018   bitmap_clear (exit_block_uses);
4019
4020   /* Stack pointer is always live at the exit.  */
4021   bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM);
4022
4023   /* Mark the frame pointer if needed at the end of the function.
4024      If we end up eliminating it, it will be removed from the live
4025      list of each basic block by reload.  */
4026
4027   if ((!reload_completed) || frame_pointer_needed)
4028     {
4029       bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM);
4030 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4031       /* If they are different, also mark the hard frame pointer as live.  */
4032       if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
4033         bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM);
4034 #endif
4035     }
4036
4037 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
4038   /* Many architectures have a GP register even without flag_pic.
4039      Assume the pic register is not in use, or will be handled by
4040      other means, if it is not fixed.  */
4041   if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
4042       && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
4043     bitmap_set_bit (exit_block_uses, PIC_OFFSET_TABLE_REGNUM);
4044 #endif
4045
4046   /* Mark all global registers, and all registers used by the
4047      epilogue as being live at the end of the function since they
4048      may be referenced by our caller.  */
4049   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4050     if (global_regs[i] || EPILOGUE_USES (i))
4051       bitmap_set_bit (exit_block_uses, i);
4052
4053   if (HAVE_epilogue && epilogue_completed)
4054     {
4055       /* Mark all call-saved registers that we actually used.  */
4056       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4057         if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i)
4058             && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
4059           bitmap_set_bit (exit_block_uses, i);
4060     }
4061
4062 #ifdef EH_RETURN_DATA_REGNO
4063   /* Mark the registers that will contain data for the handler.  */
4064   if (reload_completed && crtl->calls_eh_return)
4065     for (i = 0; ; ++i)
4066       {
4067         unsigned regno = EH_RETURN_DATA_REGNO (i);
4068         if (regno == INVALID_REGNUM)
4069           break;
4070         bitmap_set_bit (exit_block_uses, regno);
4071       }
4072 #endif
4073
4074 #ifdef EH_RETURN_STACKADJ_RTX
4075   if ((!HAVE_epilogue || ! epilogue_completed)
4076       && crtl->calls_eh_return)
4077     {
4078       rtx tmp = EH_RETURN_STACKADJ_RTX;
4079       if (tmp && REG_P (tmp))
4080         df_mark_reg (tmp, exit_block_uses);
4081     }
4082 #endif
4083
4084 #ifdef EH_RETURN_HANDLER_RTX
4085   if ((!HAVE_epilogue || ! epilogue_completed)
4086       && crtl->calls_eh_return)
4087     {
4088       rtx tmp = EH_RETURN_HANDLER_RTX;
4089       if (tmp && REG_P (tmp))
4090         df_mark_reg (tmp, exit_block_uses);
4091     }
4092 #endif
4093
4094   /* Mark function return value.  */
4095   diddle_return_value (df_mark_reg, (void*) exit_block_uses);
4096 }
4097
4098
4099 /* Return the refs of hard registers that are used in the exit block.
4100    It uses df->exit_block_uses to determine register to include.  */
4101
4102 static void
4103 df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses)
4104 {
4105   unsigned int i;
4106   bitmap_iterator bi;
4107
4108   EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi)
4109     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL,
4110                    EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0, -1, -1, VOIDmode);
4111
4112 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4113   /* It is deliberate that this is not put in the exit block uses but
4114      I do not know why.  */
4115   if (reload_completed
4116       && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM)
4117       && bb_has_eh_pred (EXIT_BLOCK_PTR)
4118       && fixed_regs[ARG_POINTER_REGNUM])
4119     df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL,
4120                    EXIT_BLOCK_PTR, NULL, DF_REF_REG_USE, 0, -1, -1, VOIDmode);
4121 #endif
4122
4123   df_canonize_collection_rec (collection_rec);
4124 }
4125
4126
4127 /* Record the set of hard registers that are used in the exit block.
4128    It uses df->exit_block_uses to determine which bit to include.  */
4129
4130 static void
4131 df_record_exit_block_uses (bitmap exit_block_uses)
4132 {
4133   struct df_collection_rec collection_rec;
4134   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4135   collection_rec.use_vec = VEC_alloc (df_ref, stack, FIRST_PSEUDO_REGISTER);
4136
4137   df_exit_block_uses_collect (&collection_rec, exit_block_uses);
4138
4139   /* Process bb_refs chain */
4140   df_refs_add_to_chains (&collection_rec, BASIC_BLOCK (EXIT_BLOCK), NULL);
4141   VEC_free (df_ref, stack, collection_rec.use_vec);
4142 }
4143
4144
4145 /* Update the uses in the exit block.  */
4146
4147 void
4148 df_update_exit_block_uses (void)
4149 {
4150   bitmap refs = BITMAP_ALLOC (&df_bitmap_obstack);
4151   bool changed = false;
4152
4153   df_get_exit_block_use_set (refs);
4154   if (df->exit_block_uses)
4155     {
4156       if (!bitmap_equal_p (df->exit_block_uses, refs))
4157         {
4158           struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK);
4159           df_ref_chain_delete_du_chain (bb_info->artificial_uses);
4160           df_ref_chain_delete (bb_info->artificial_uses);
4161           bb_info->artificial_uses = NULL;
4162           changed = true;
4163         }
4164     }
4165   else
4166     {
4167       struct df_scan_problem_data *problem_data
4168         = (struct df_scan_problem_data *) df_scan->problem_data;
4169       df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps);
4170       changed = true;
4171     }
4172
4173   if (changed)
4174     {
4175       df_record_exit_block_uses (refs);
4176       bitmap_copy (df->exit_block_uses, refs);
4177       df_set_bb_dirty (BASIC_BLOCK (EXIT_BLOCK));
4178     }
4179   BITMAP_FREE (refs);
4180 }
4181
4182 static bool initialized = false;
4183
4184
4185 /* Initialize some platform specific structures.  */
4186
4187 void
4188 df_hard_reg_init (void)
4189 {
4190 #ifdef ELIMINABLE_REGS
4191   int i;
4192   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
4193 #endif
4194   if (initialized)
4195     return;
4196
4197   /* Record which registers will be eliminated.  We use this in
4198      mark_used_regs.  */
4199   CLEAR_HARD_REG_SET (elim_reg_set);
4200
4201 #ifdef ELIMINABLE_REGS
4202   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
4203     SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
4204 #else
4205   SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
4206 #endif
4207
4208   initialized = true;
4209 }
4210
4211
4212 /* Recompute the parts of scanning that are based on regs_ever_live
4213    because something changed in that array.  */
4214
4215 void
4216 df_update_entry_exit_and_calls (void)
4217 {
4218   basic_block bb;
4219
4220   df_update_entry_block_defs ();
4221   df_update_exit_block_uses ();
4222
4223   /* The call insns need to be rescanned because there may be changes
4224      in the set of registers clobbered across the call.  */
4225   FOR_EACH_BB (bb)
4226     {
4227       rtx insn;
4228       FOR_BB_INSNS (bb, insn)
4229         {
4230           if (INSN_P (insn) && CALL_P (insn))
4231             df_insn_rescan (insn);
4232         }
4233     }
4234 }
4235
4236
4237 /* Return true if hard REG is actually used in the some instruction.
4238    There are a fair number of conditions that affect the setting of
4239    this array.  See the comment in df.h for df->hard_regs_live_count
4240    for the conditions that this array is set. */
4241
4242 bool
4243 df_hard_reg_used_p (unsigned int reg)
4244 {
4245   gcc_assert (df);
4246   return df->hard_regs_live_count[reg] != 0;
4247 }
4248
4249
4250 /* A count of the number of times REG is actually used in the some
4251    instruction.  There are a fair number of conditions that affect the
4252    setting of this array.  See the comment in df.h for
4253    df->hard_regs_live_count for the conditions that this array is
4254    set. */
4255
4256
4257 unsigned int
4258 df_hard_reg_used_count (unsigned int reg)
4259 {
4260   gcc_assert (df);
4261   return df->hard_regs_live_count[reg];
4262 }
4263
4264
4265 /* Get the value of regs_ever_live[REGNO].  */
4266
4267 bool
4268 df_regs_ever_live_p (unsigned int regno)
4269 {
4270   return regs_ever_live[regno];
4271 }
4272
4273
4274 /* Set regs_ever_live[REGNO] to VALUE.  If this cause regs_ever_live
4275    to change, schedule that change for the next update.  */
4276
4277 void
4278 df_set_regs_ever_live (unsigned int regno, bool value)
4279 {
4280   if (regs_ever_live[regno] == value)
4281     return;
4282
4283   regs_ever_live[regno] = value;
4284   if (df)
4285     df->redo_entry_and_exit = true;
4286 }
4287
4288
4289 /* Compute "regs_ever_live" information from the underlying df
4290    information.  Set the vector to all false if RESET.  */
4291
4292 void
4293 df_compute_regs_ever_live (bool reset)
4294 {
4295   unsigned int i;
4296   bool changed = df->redo_entry_and_exit;
4297
4298   if (reset)
4299     memset (regs_ever_live, 0, sizeof (regs_ever_live));
4300
4301   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4302     if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
4303       {
4304         regs_ever_live[i] = true;
4305         changed = true;
4306       }
4307   if (changed)
4308     df_update_entry_exit_and_calls ();
4309   df->redo_entry_and_exit = false;
4310 }
4311
4312 \f
4313 /*----------------------------------------------------------------------------
4314   Dataflow ref information verification functions.
4315
4316   df_reg_chain_mark (refs, regno, is_def, is_eq_use)
4317   df_reg_chain_verify_unmarked (refs)
4318   df_refs_verify (VEC(stack,df_ref)*, ref*, bool)
4319   df_mws_verify (mw*, mw*, bool)
4320   df_insn_refs_verify (collection_rec, bb, insn, bool)
4321   df_bb_refs_verify (bb, refs, bool)
4322   df_bb_verify (bb)
4323   df_exit_block_bitmap_verify (bool)
4324   df_entry_block_bitmap_verify (bool)
4325   df_scan_verify ()
4326 ----------------------------------------------------------------------------*/
4327
4328
4329 /* Mark all refs in the reg chain.  Verify that all of the registers
4330 are in the correct chain.  */
4331
4332 static unsigned int
4333 df_reg_chain_mark (df_ref refs, unsigned int regno,
4334                    bool is_def, bool is_eq_use)
4335 {
4336   unsigned int count = 0;
4337   df_ref ref;
4338   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4339     {
4340       gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4341
4342       /* If there are no def-use or use-def chains, make sure that all
4343          of the chains are clear.  */
4344       if (!df_chain)
4345         gcc_assert (!DF_REF_CHAIN (ref));
4346
4347       /* Check to make sure the ref is in the correct chain.  */
4348       gcc_assert (DF_REF_REGNO (ref) == regno);
4349       if (is_def)
4350         gcc_assert (DF_REF_REG_DEF_P (ref));
4351       else
4352         gcc_assert (!DF_REF_REG_DEF_P (ref));
4353
4354       if (is_eq_use)
4355         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE));
4356       else
4357         gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0);
4358
4359       if (DF_REF_NEXT_REG (ref))
4360         gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref);
4361       count++;
4362       DF_REF_REG_MARK (ref);
4363     }
4364   return count;
4365 }
4366
4367
4368 /* Verify that all of the registers in the chain are unmarked.  */
4369
4370 static void
4371 df_reg_chain_verify_unmarked (df_ref refs)
4372 {
4373   df_ref ref;
4374   for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref))
4375     gcc_assert (!DF_REF_IS_REG_MARKED (ref));
4376 }
4377
4378
4379 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4380
4381 static bool
4382 df_refs_verify (VEC(df_ref,stack) *new_rec, df_ref *old_rec,
4383                 bool abort_if_fail)
4384 {
4385   unsigned int ix;
4386   df_ref new_ref;
4387
4388   for (ix = 0; VEC_iterate (df_ref, new_rec, ix, new_ref); ++ix)
4389     {
4390       if (*old_rec == NULL || !df_ref_equal_p (new_ref, *old_rec))
4391         {
4392           if (abort_if_fail)
4393             gcc_assert (0);
4394           else
4395             return false;
4396         }
4397
4398       /* Abort if fail is called from the function level verifier.  If
4399          that is the context, mark this reg as being seem.  */
4400       if (abort_if_fail)
4401         {
4402           gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
4403           DF_REF_REG_UNMARK (*old_rec);
4404         }
4405
4406       old_rec++;
4407     }
4408
4409   if (abort_if_fail)
4410     gcc_assert (*old_rec == NULL);
4411   else
4412     return *old_rec == NULL;
4413   return false;
4414 }
4415
4416
4417 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4418
4419 static bool
4420 df_mws_verify (VEC(df_mw_hardreg_ptr,stack) *new_rec,
4421                struct df_mw_hardreg **old_rec,
4422                bool abort_if_fail)
4423 {
4424   unsigned int ix;
4425   struct df_mw_hardreg *new_reg;
4426
4427   for (ix = 0; VEC_iterate (df_mw_hardreg_ptr, new_rec, ix, new_reg); ++ix)
4428     {
4429       if (*old_rec == NULL || !df_mw_equal_p (new_reg, *old_rec))
4430         {
4431           if (abort_if_fail)
4432             gcc_assert (0);
4433           else
4434             return false;
4435         }
4436       old_rec++;
4437     }
4438
4439   if (abort_if_fail)
4440     gcc_assert (*old_rec == NULL);
4441   else
4442     return *old_rec == NULL;
4443   return false;
4444 }
4445
4446
4447 /* Return true if the existing insn refs information is complete and
4448    correct. Otherwise (i.e. if there's any missing or extra refs),
4449    return the correct df_ref chain in REFS_RETURN.
4450
4451    If ABORT_IF_FAIL, leave the refs that are verified (already in the
4452    ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4453    verification mode instead of the whole function, so unmark
4454    everything.
4455
4456    If ABORT_IF_FAIL is set, this function never returns false.  */
4457
4458 static bool
4459 df_insn_refs_verify (struct df_collection_rec *collection_rec,
4460                      basic_block bb,
4461                      rtx insn,
4462                      bool abort_if_fail)
4463 {
4464   bool ret1, ret2, ret3, ret4;
4465   unsigned int uid = INSN_UID (insn);
4466   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4467
4468   df_insn_refs_collect (collection_rec, bb, insn_info);
4469
4470   if (!DF_INSN_UID_DEFS (uid))
4471     {
4472       /* The insn_rec was created but it was never filled out.  */
4473       if (abort_if_fail)
4474         gcc_assert (0);
4475       else
4476         return false;
4477     }
4478
4479   /* Unfortunately we cannot opt out early if one of these is not
4480      right because the marks will not get cleared.  */
4481   ret1 = df_refs_verify (collection_rec->def_vec, DF_INSN_UID_DEFS (uid),
4482                          abort_if_fail);
4483   ret2 = df_refs_verify (collection_rec->use_vec, DF_INSN_UID_USES (uid),
4484                          abort_if_fail);
4485   ret3 = df_refs_verify (collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid),
4486                          abort_if_fail);
4487   ret4 = df_mws_verify (collection_rec->mw_vec, DF_INSN_UID_MWS (uid),
4488                        abort_if_fail);
4489   return (ret1 && ret2 && ret3 && ret4);
4490 }
4491
4492
4493 /* Return true if all refs in the basic block are correct and complete.
4494    Due to df_ref_chain_verify, it will cause all refs
4495    that are verified to have DF_REF_MARK bit set.  */
4496
4497 static bool
4498 df_bb_verify (basic_block bb)
4499 {
4500   rtx insn;
4501   struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
4502   struct df_collection_rec collection_rec;
4503
4504   memset (&collection_rec, 0, sizeof (struct df_collection_rec));
4505   collection_rec.def_vec = VEC_alloc (df_ref, stack, 128);
4506   collection_rec.use_vec = VEC_alloc (df_ref, stack, 32);
4507   collection_rec.eq_use_vec = VEC_alloc (df_ref, stack, 32);
4508   collection_rec.mw_vec = VEC_alloc (df_mw_hardreg_ptr, stack, 32);
4509
4510   gcc_assert (bb_info);
4511
4512   /* Scan the block, one insn at a time, from beginning to end.  */
4513   FOR_BB_INSNS_REVERSE (bb, insn)
4514     {
4515       if (!INSN_P (insn))
4516         continue;
4517       df_insn_refs_verify (&collection_rec, bb, insn, true);
4518       df_free_collection_rec (&collection_rec);
4519     }
4520
4521   /* Do the artificial defs and uses.  */
4522   df_bb_refs_collect (&collection_rec, bb);
4523   df_refs_verify (collection_rec.def_vec, df_get_artificial_defs (bb->index), true);
4524   df_refs_verify (collection_rec.use_vec, df_get_artificial_uses (bb->index), true);
4525   df_free_collection_rec (&collection_rec);
4526
4527   return true;
4528 }
4529
4530
4531 /* Returns true if the entry block has correct and complete df_ref set.
4532    If not it either aborts if ABORT_IF_FAIL is true or returns false.  */
4533
4534 static bool
4535 df_entry_block_bitmap_verify (bool abort_if_fail)
4536 {
4537   bitmap entry_block_defs = BITMAP_ALLOC (&df_bitmap_obstack);
4538   bool is_eq;
4539
4540   df_get_entry_block_def_set (entry_block_defs);
4541
4542   is_eq = bitmap_equal_p (entry_block_defs, df->entry_block_defs);
4543
4544   if (!is_eq && abort_if_fail)
4545     {
4546       print_current_pass (stderr);
4547       fprintf (stderr, "entry_block_defs = ");
4548       df_print_regset (stderr, entry_block_defs);
4549       fprintf (stderr, "df->entry_block_defs = ");
4550       df_print_regset (stderr, df->entry_block_defs);
4551       gcc_assert (0);
4552     }
4553
4554   BITMAP_FREE (entry_block_defs);
4555
4556   return is_eq;
4557 }
4558
4559
4560 /* Returns true if the exit block has correct and complete df_ref set.
4561    If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4562
4563 static bool
4564 df_exit_block_bitmap_verify (bool abort_if_fail)
4565 {
4566   bitmap exit_block_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4567   bool is_eq;
4568
4569   df_get_exit_block_use_set (exit_block_uses);
4570
4571   is_eq = bitmap_equal_p (exit_block_uses, df->exit_block_uses);
4572
4573   if (!is_eq && abort_if_fail)
4574     {
4575       print_current_pass (stderr);
4576       fprintf (stderr, "exit_block_uses = ");
4577       df_print_regset (stderr, exit_block_uses);
4578       fprintf (stderr, "df->exit_block_uses = ");
4579       df_print_regset (stderr, df->exit_block_uses);
4580       gcc_assert (0);
4581     }
4582
4583   BITMAP_FREE (exit_block_uses);
4584
4585   return is_eq;
4586 }
4587
4588
4589 /* Return true if df_ref information for all insns in all blocks are
4590    correct and complete.  */
4591
4592 void
4593 df_scan_verify (void)
4594 {
4595   unsigned int i;
4596   basic_block bb;
4597   bitmap regular_block_artificial_uses;
4598   bitmap eh_block_artificial_uses;
4599
4600   if (!df)
4601     return;
4602
4603   /* Verification is a 4 step process. */
4604
4605   /* (1) All of the refs are marked by going thru the reg chains.  */
4606   for (i = 0; i < DF_REG_SIZE (df); i++)
4607     {
4608       gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false)
4609                   == DF_REG_DEF_COUNT(i));
4610       gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false)
4611                   == DF_REG_USE_COUNT(i));
4612       gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true)
4613                   == DF_REG_EQ_USE_COUNT(i));
4614     }
4615
4616   /* (2) There are various bitmaps whose value may change over the
4617      course of the compilation.  This step recomputes them to make
4618      sure that they have not slipped out of date.  */
4619   regular_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4620   eh_block_artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
4621
4622   df_get_regular_block_artificial_uses (regular_block_artificial_uses);
4623   df_get_eh_block_artificial_uses (eh_block_artificial_uses);
4624
4625   bitmap_ior_into (eh_block_artificial_uses,
4626                    regular_block_artificial_uses);
4627
4628   /* Check artificial_uses bitmaps didn't change. */
4629   gcc_assert (bitmap_equal_p (regular_block_artificial_uses,
4630                               df->regular_block_artificial_uses));
4631   gcc_assert (bitmap_equal_p (eh_block_artificial_uses,
4632                               df->eh_block_artificial_uses));
4633
4634   BITMAP_FREE (regular_block_artificial_uses);
4635   BITMAP_FREE (eh_block_artificial_uses);
4636
4637   /* Verify entry block and exit block. These only verify the bitmaps,
4638      the refs are verified in df_bb_verify.  */
4639   df_entry_block_bitmap_verify (true);
4640   df_exit_block_bitmap_verify (true);
4641
4642   /* (3) All of the insns in all of the blocks are traversed and the
4643      marks are cleared both in the artificial refs attached to the
4644      blocks and the real refs inside the insns.  It is a failure to
4645      clear a mark that has not been set as this means that the ref in
4646      the block or insn was not in the reg chain.  */
4647
4648   FOR_ALL_BB (bb)
4649     df_bb_verify (bb);
4650
4651   /* (4) See if all reg chains are traversed a second time.  This time
4652      a check is made that the marks are clear. A set mark would be a
4653      from a reg that is not in any insn or basic block.  */
4654
4655   for (i = 0; i < DF_REG_SIZE (df); i++)
4656     {
4657       df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i));
4658       df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i));
4659       df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i));
4660     }
4661 }