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