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