gcc/df-scan.c

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